Exercise Goal: To learn how the existing System V shared ...



Kernel Projects for Linux Exercise #6

Managing Shared Memory using a Dynamic Data Structure

CS-450-3: Operating Systems

Fall 2003

John Bird

Thomas Fortmuller

Jason Gallick

Vito Malta

Kristoffer Wright

Table Of Contents

INTRODUCTION 1

SHARED MEMORY 1

Overview 1

Concept of Shared Memory 1

Contents of Shared Memory 1

How Shared Memory is Used 1-2

ABOUT THE UNMODIFIED SHM.C FILE 2

Overview 2

The Importance of Shm_get, new_seg and shmid_kernel 2-3

Find_key and the race condition 3

The Importance of Sys_shmctl, sys_shmat, and sys_shmdt 3

Variables and Functions of Shm.c 4-5

TEST PROGRAM – CS450PROJ.C 5

Developing the Program 5

Executing the Program 5

Importance of the Program 6

ABOUT THE MODIFIED SHM.C FILE 6

Overview 6

List Structure 6

Referencing a List Element 6

Appending a Node to the List 7

Modifying an Element within the List 7

List Initialization 7

Insertion of List Manipulation Functions 8

PROBLEMS 8

Redhat and Mandrake 8

Compiling the Kernel 8-9

Table Of Contents (con’t)

LINKED LIST VS ARRAY

SHARED MEMORY SCHEMES 9

Arrays 9

Linked Lists 9

CPU Efficiency Usage or Memory Usage 9

BIBLIOGRAPHY 10

APPENDIX A Unmodified shm.c A1-A14

APPENDIX B cs450proj.c A15-A16

APPENDIX C Modified shm.c A17-A29

Introduction

Our group selected programming assignment 6 Gary Nutts book Kernel Projects for Linux.. The programming assignment was broken down into 4 steps. Each step explained what our grouped needed to accomplish in order to complete our term project. The book began by briefly explaining what shared memory was and second how Linux implemented shared memory. The third step described the purpose of the exercise we had chosen. Our goal was to change the structure of the kernel from a static array to a linked list. The last step in the book gave us valuable advice on how to approach the exercise. Our paper will comprehensively explain what shared memory is, how Linux’s kernel implements shared memory, the test program we created, how we altered Linux’s kernel, and the problems we overcame throughout our assignment.

Shared Memory

Overview

A very basic program is simply a single process that manages all of its own data. No communication takes place between it and other processes. However, most programs are not so simple; most programs consist of multiple processes communicating with each other. The avenue in which this communication takes place is via shared memory.

Concept of Shared Memory

The concept of shared memory refers to a common block of main memory that multiple processes can access. If one process changes the data in the shared block of memory, then all processes can know about that change. A shared block of memory is logically part of the memory manager. This mechanism was originally developed as part of the InterProcess Communication (IPC) mechanism for System V UNIX, and has been passed down to Linux – in all its variations.

Contents of Shared Memory

When a process is created, it is allocated a certain amount of virtual memory. Most of this space is unused - only a small portion is used to store the compiled code, static data, the stack, and the heap. The remaining addresses are initially unused, but will be used to store the data created by the process.

How Shared Memory is Used

A block of main memory may be defined as a block of shared memory. This block can then be mapped into the virtual memory of a certain process. Now, this process is able to read from and write to the block of shared memory as if it were its own block of memory. Other processes can also map the block of shared memory to their own virtual memories. Now, all processes that have the block of shared memory mapped to their virtual memories can communicate with each other using the common block of shared memory. A diagram of this mechanism is shown below:

[pic]

About the unmodified shm.c file

Overview

Shm.c is the file in the Linux kernel that implements shared memory. The beginning of the shared memory process of shm.c always starts with shm_init. When shm_init is first called, it fills a static array (shm_segs), also called a table, that holds pointers to shared segment structures and marks each index as unused. Shm_init accomplishes this by using a flag, IPC_UNUSED. Two important variables used throughout the various functions in shm.c are SHMNI and SHMALL. SHMNI is the size of the shm_segs array and represents the total number of shared memory ids. SHMALL is the system limit on shared memory. There are also two flags that are used in the shm_segs array, which are IPC_UNUSED and IPC_NOID. IPC_UNUSED denotes that the entry in the array is not being used, and the IPC_NOID flag denotes that no identifier has been attached to the entry yet.

The Importance of Shm_get, new_seg and shmid_kernel

Shmid_kernel is the data structure that the pointers in shm_segs point to. The shmid_kernel structure is made up of 10 different variables, 2 of which are structures themselves. It is interesting to note that a kern_ipc_perm struct is part of the shmid_kernel struct. The significance of this is that the kern_ipc_perm struct contains the values for some of UNIX’s signature innovations, such as gid (group id) and uid (user id). The next step involves shm_get, which is used to create and reserve entries in the array. Depending on the parameters it is given, shm_get can behave differently. It can look for a particular entry in the shm_segs array using find_key, which cycles through shm_segs, returning a value describing the state of the entry. It can also create a new segment in memory via the new_seg function if the key passed in the parameter is IPC_PRIVATE or IPC_CREAT. The new_seg function cycles through the array entries of shm_segs until it finds an entry where the IPC_UNUSED flag is set, signifying an empty index. It then checks to see whether it has enough room to accommodate a segment of the requested size, and whether it has enough pages in system wide memory. If there isn’t enough memory the function returns an error of ENOMOM. However, if there is enough memory and enough pages, then the shmid_kernel struct pointer is placed in shm_segs.

Find_key and the race condition

In find_key the following code is an important entry because of find_key’s interaction with new_seg. The complete method can be found in Appendix A on lines 57-71.

while ((shp = shm_segs[id]) == IPC_NOID)

sleep_on (&shm_lock);

if (shp == IPC_UNUSED)

continue;

if (key == shp->u.shm_perm.key)

return id;

The first entry under the while loop is a sleep_on statement. It is necessary because of the race condition between new_seg and find_key. While find_key is searching the array shm_segs, a problem could occur if new_seg is still allocating. For instance, if a new segment is being added and then find_key is run on that segment, there might be an erroneous result if new_seg hadn’t finished marking the entry as reserved (switching the flag IPC_UNUSED). The sleep command forces the find_key function to wait in a queue (shm_lock) until the new_seg function finishes, and when it does so the new_seg function releases the first entry of the queue.

The Importance of Sys_shmctl, sys_shmat, and sys_shmdt

The sys_shmctl function is a large case statement that evaluates a passed in command variable and takes the appropriate action. It is a system call that handles a variety of different things, including providing info about a shared memory segment and locking a segment into memory (requires root privilege). Sys_shmat is the function that actually maps the memory segment into the address space of a process. It does this by checking the virtual address space of the process for an empty space, making sure it will fit into the space, and finally mapping it into the page table of the process with the functions shm_map and insert_attach. Sys_shmdt is the function that detaches a shared memory segment from a process. The function looks through the memory descriptors of a process, and if it finds a segment that needs to be released, it unmaps it.

Variables and Functions of Shm.c

Below is reference table describing the variables and functions found in the unmodified shm.c file. The code for the shm.c file can be found in Appendix A.

|Find_key |Function |Finds a specific instance in the|

| | |shm_seg array |

|Max_shmid |Integer variable |Threshold for id limits |

|Name |Type |Description |

|New_seg |Function |Searches the array for an unused|

| | |index and then marks that index |

| | |as reserved. |

|Shm_get |Function |Searches through the shared |

| | |memory array for an entry. Uses |

| | |new_seg or find_key. |

|Shm_init |Function |Initializes shm_segs to with |

| | |IPC_UNUSED |

|Shm_rss |Integer variable |Shared memory pages that are |

| | |actually in memory |

|Shm_segs |Array |Static array of shmid_kernel |

| | |pointers. |

|Shm_swp |Integer variable |Number of shared memory pages in|

| | |swap |

|Shm_tot |Integer variable |Total number of shared memory |

| | |pages |

|SHMALL |Defined as ((SHMMAX/PAGESIZE)*(SHMNI/16)) |Max number of shared memory |

| | |pages on system |

|Shmid_kernel |Structure |Contains information private to |

| | |the kernel. |

|SHMNI |Integer variable(defined as 4096) |Describes total number of shared|

| | |memory ids and segments |

|Sys_shmat |Function |Maps shared memory block into |

| | |process’s address space |

|Sys_shmctl |Function |Large switch case that provides |

| | |miscellaneous functionality |

|Sys_shmdt |Function |Detaches shared memory mapping |

|Vm_area_struct |Structure |Contains a pointer to swap out |

| | |virtual memory back into |

| | |physical memory |

Test program - cs450proj.c

Developing the Program

We wrote a test program cs450proj.c (see appendix A) before we made any changes to the shm.c file that what would use shared memory. The cs450proj.c needed to demonstrate how shared memory worked by creating two processes that accessed the same segments of shared memory. We began by implementing the book’s example of shared memory. However, the book’s example showed a single block of shared memory and we needed to have multiple blocks. To implement multiple segments of shared memory we created a second variable to reference the second segments memory location. Then copied the code that included the first memory segments name and replaced the first name with the second memory segments name. The complete cs450proj.c file is in Appendix B lines 1-114.

Executing the Program

When executed, the finished test program first displayed the two memory locations. Then prompted the user to enter a string to be stored in the child’s first segment of shared memory and another string to be stored in the child’s second segment of shared memory. Next the program prints the first and second segment’s contents to the screen. The last step is to print the child’s memory locations to show that the both segments were being recycled each time the program ran.

Importance of the Program

This test program was vital to our overall assignment. We had to prove that Linux’s shared memory was properly working before and after we changed the shm.c file from a static array to a linked list. Otherwise the shm.c file could have compiled successfully without being fully operational and we would not have been able to find the correct error.

About the modified shm.c

Overview

The programming part of our project consisted of modifying the source file shm.c in six steps. The first step was to create a data structure representing a node in a linked list. The second was to write a function that will return a reference to a shmid_kernel structure within the linked list based on an integer argument. The third was to create a function that would insert a new node into the linked list. The fourth was to rewrite the shm_segs array initialization code to instead initialize the linked list. The fifth step was to write a function that could modify a shmid_kernel structure within the linked list. The final task was to incorporate our linked list into the original code by instantiating and initializing the list, replacing all instances of statements containing “= shm_segs[x]” with calls to the shmid_kernel referencing function, and replacing all assignments of the form “shm_segs[x] =” with the shmid_kernel modification function.

List Structure

The first task was to design a structure that would be the basis for a linked list of shmid_kernel structures. The traditional form of a linked list is to create a “head” node, which contains, along with any number of variables, a pointer that references the next node in the list or NULL if the node is the last in the list. We chose to name our node structure “shm_list”, and included in it a reference to a shmid_kernel structure, and a pointer to the next node in the list. The completed shm_list structure appears in Appendix C on lines 47-63

Referencing a List Element

The next step was to write a function that would take an integer argument and return a reference to the shmid_kernel structure that was stored in the node at the nth position in the list, where n is the integer argument. This will effectively replace the shm_segs[n] statement. We chose to implement the function as a loop, using an integer counter variable and a placeholder variable of type shm_list. First, the counter variable is initialized to NULL and the placeholder is assigned to point to the head of the list. Then, as long as the counter is less than the integer argument and the placeholder’s next variable is not NULL, the placeholder is assigned the value of its own next pointer. Finally, the placeholder is returned. There is no error checking done to ensure that the node returned is actually the one desired, i.e. if the number six is passed in, and there are only five elements in the list, then the fifth element would be returned. We deemed that this was acceptable as there is no error checking of this type done in the original code, only a simple modulus operation to ensure that the array bounds are maintained. Furthermore, if such an error occurred, it would be the fault of the calling process, not the shared memory code. The finished function appears Appendix C on lines 70-88.

Appending a Node to the List

For the next step, we wrote a function that adds a new node to the end of the list. This function has no counterpart in the original code, where a “no space” error, ENOSPC, was returned if an available element was sought in a full array. The call to this function will be in the midst of original code that uses an integer to store the position within the list of an unused shmid_kernel variable. In order to maintain compatibility with the surrounding code, the function will return the location within the list of the created element, or zero if there is not enough memory to create a new node. The function uses a for loop to find the end of the list by continuing through it until the current node’s next pointer equals zero. Next, kmalloc is used to allocate memory for the new node. The new node’s next variable is set to 0, since it is the end of the list, and its shmid_kernel variable is set to IPC_NOID. This is done to assure that the findkey function does not attempt to return the newly created node to another process before it is allocated to the one currently requesting it. Finally, the current end of the list has its next pointer set to the new node’s address. If zero is returned from this function, a “no memory” error, ENOMEM, is returned by the calling function, newseg. Otherwise, the return value is assigned to an integer in the original code. The finished function appears Appendix C on lines 90-127.

Modifying an Element Within the List

The final function that we had to write was one that could modify a shmid_kernel variable within the list. The function takes an integer parameter to specify which shmid_kernel variable to change, and a shmid_kernel pointer parameter will be used as the value to be assigned. The function will loop through the list until the nth element is reached, n being the integer parameter, and then assign the shmid_kernel parameter’s value to the selected element’s shmid_kernel variable. The finished function appears Appendix C on lines 162-181.

List Initialization

Next, we had to replace the original array initialization code with our own code that creates and initializes the head of the list. We declared a static global shm_list pointer called head. Inside of the original shm_init function, kmalloc was used to allocate memory space for head, its next pointer was set to NULL, and its shmid_kernel pointer was set to the constant value IPC_UNUSED, which signifies it as free to be allocated. The code that was added is shown in Appendix C on lines 142-154.

Insertion of List Manipulation Functions

Our final task was to replace all the occurrences in the code of shm_segs[x] with our own functions. All statements of the form some_variable = shm_segs[x] were replaced with some_variable = findseg(x) and those of the form shm_segs[x] = some_variable were replaced by setseg(x,some_variable). This completed the necessary modifications to the shm.c file and the kernel was now ready to be recompiled.

Problems

Redhat and Mandrake

When our group first began looking at the shm.c file in the ipc directory, we were confused. There were several lines of code in the file that were not described in Gary Nutt’s Kernel Projects for Linux. We had installed and were using Linux Red Hat 9, kernel version 2.4, while Nutt describes Linux Mandrake 7, kernel version 2.2 in his book. After discovering that the text was outdated, we installed Mandrake 7, kernel version 2.2 so we could use the book as a reference.

Compiling the Kernel

Changing the shared memory scheme in shm.c did not pose a terribly difficult problem, however, compiling the kernel was not as simple. Makefiles are included in Linux, which are designed to automatically build and install the new or augmented kernel. Five separate make commands turns the difficult compiling process into a relatively simple process.

The five make commands we used are below:

# make clean

# make oldconfig

# make depend

# make

# make bzImage

However, if the kernel is not error-free, make depend would exit with error messages. It is necessary to have the kernel test compile successfully prior to using the make commands. We attempted to test compile by typing:

This attempted compile resulted in several hundred errors. Mandrake has no command line screen buffer and because we had so many lines of errors we could not view all of them. We were required to stop the compiler milli-seconds after we compiled, in effort to see where the first errors occurred. The first errors were inane, reporting that files did not recognize shm.c. The errors did not relate to our recently added code. We attempted to compile the unmodified shm.c code, only to be frustrated by the same errors.

To properly compile the kernel, certain environment variables must be passed to gcc at compile time. In order to find these variables we used the original version of the kernel and redirected the output from make to a text file. We then ran GREP (Global Regular Expression Print) on the text file for shm.c we found the following:

These multiple lines of code are required to compile the Linux kernel.

Linked List vs. Array Shared Memory Schemes

Arrays

Implementing an array for the kernel has pros and cons. The array does allow for fast access to its memory contents but that could be the only benefit of the array. An array has a fixed size and an error will occur when attempting to access an index of the array outsides the array’s boundaries. In order to prevent an error during execution of the shm.c program, the static array used in shm.c is initialized to allocate 4096 memory spaces that are each 4096 long. When the program is first executed the static array is empty and in turn is wasting a significant amount of space.

Linked Lists

A linked list is another form of data storage. It creates a list of objects. Each object has a pointer to memory and a pointer to the next object in the list. A linked list does not waste memory space but it is very inefficient when attempting to search. To search a linked list you must start from the head of the list and loop through the list until the desire location is reached. Deleting is also inefficient since it involves search the list to find the object to delete.

CPU Efficiency Usage or Memory Usage

Originally the kernel was written to store its data in an array. Our project was to change the way data was stored from a static array to a linked list. Determines which storage structure is better boils down to the static array’s large amount of memory usage and linked list’s inefficient usage of the CPU. When comparing memory usage to CPU usage, efficient usage of the CPU is much more important then the amount of memory being used. Thus, our project actually made the kernel worse by changing the array to a listed list.

BIBLOGRAPHY

Gleditcsh, Arne & Gjermshus, Per (2003). “Gary Nutt Exercise 6.” URL:



Kampe, Mark (2000). “Gary Nutt Exercise 6.” URL:



SystemV.doc

Nutt, Gary (2001). Kernel Projects for Linux. New York, NY: Addison Wesley.

Shulman, Sherri (2001). “Gary Nutt Exercise 6.” URL:



lec.8.29.html

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download