EECE-4029 Operating Systems Fall 2016
Lab 8

processes, mutex, semaphores, memory management, producer-consumer, files, deadlock, more..

Memory Management: buddy allocator

Due: Nov 4 (submit instructions: here)

Rationale:
    Begin development of a very simple virtual memory manager.
 
Lab:
In this homework a buddy allocator will be developed. The allocator will be implemented as a kernel module. When the module is loaded it will malloc 212*212 of space from the operating system. It will use that space to satisfy requests from a user. Access to the allocator will be via the following procedures:
  • get_mem(int mem, int size):
    Request a block of memory of size size bytes from the memory manager whose handle is mem. Returns an integer which is a reference to the block (or a negative number on failure) and is denoted ref below.
  • free_mem(int mem, int ref):
    Free the block of memory referenced as ref from the memory manager whose handle is mem. Returns 0 on success and -1 on error.
  • write_mem(int mem, int ref, char *buf):
    Writes the contents of the buffer buf to the memory block ref of the memory manager whose handle is mem. Stops writing when the first 0 is encountered in buf. Returns the number of bytes written or a negative number on error.
  • read_mem(int mem, int ref, char *buf, int size):
    Reads size bytes from the memory block ref of memory manager mem and returns the result in buf. The return value of read_mem is the number of bytes read or a negative number on error.
A sample use of the above, minus error detection, is as follows:
   int mem, ref;
   char buffer[4096];

   mem = open("/dev/mem_dev", 0);
   ref = get_mem(mem, 100);
   sprintf(buffer, "Hello buddy");
   write_mem(mem, ref, buffer);
   read_mem(mem, ref+3, buffer, 10);
   printf("buffer: %s\n", buffer);  /* buffer: lo buddy */
   free_mem(mem, ref);
   close(mem);
The buddy allocator should maintain a table that keeps track of all the allocated and all the free pages. The allocator should merge free buddy pages when possible. The allocator should cause get_mem to return an error if the request cannot be granted, should cause free_mem to return an error if the specified reference is not valid (the page is not allocated or is out of range), should minimally cause read_mem to return an error if the request is not completely inside the allocated space, and should minimally cause write_mem to return an error if the request would overflow the specified memory block.
 
Assistance:
  1. Use driver-07.c and ioctl_07.c with include file chardev.h, Makefile and scripts load and unload as a template.
  2. Use kmalloc(<space>, GFP_KERNEL) to get space for the allocator like this:
      static char *memory;  /* defined globally */
      #define MEM_SIZE (1 << 12)
      ...
      memory = kmalloc(MEM_SIZE, GFP_KERNEL);
    
  3. Use copy_from_user in static ssize_t write (...) like this:
      char *ptr;   /* defined globally */
      ...
      ptr = &memory[ref];  /* in ioctl - ref is from the user */
      ...
      static write ssize_t write (file, buff, len, off) { /* types omitted */
         ...
         size_t length = min(len, (size_t)MEM_SIZE);
         val = copy_from_user(ptr, buff, length);
         ...
      }
    
    You get a warning if you do not save the return value of copy_from_user.
  4. Use copy_to_user analogously.