memory.c

This a framework to test new ideas in transmission technology. Actual development is a LDPC-coder in

/***************************************************************************
         memory.c  -  RTLinux kernel module for memory allocation
                            -------------------
    begin                :  2002
    authors              :  Silvio Boehler
    emails               :  [e-mail]
 ***************************************************************************/

/***************************************************************************
                                 Changes
                                 -------
 date - name - description
 03/04/07 - ineiti - added block-allocation on request
 03/06/04 - ineiti - added 16-byte alignement
 
 **************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/


#define DBG_LVL 0

/**
 * The general system-include to differentiate between user-space and
 * kernel-spaces
 */
#include "system.h"

/**
 * The interface for this module
 */

#include "memory.h"

/**
 * Debugging
 */

#include "debugging.h"

/**
 * These constants define the minimum and maximum size of blocks (in
 * powers of 2). This overrides the parameters passed by the
 * users. Block numbers specified for sizes outside of this range are
 * ignored. The minimum size is usually the size of a processor word,
 * 2 or 3 in most cases.
 */

#define MIN_BLOCK_PWR_2  2
#define MAX_BLOCK_PWR_2 30
#define BLOCK_FREE 0x12345678
#define BLOCK_USED 0x87654321
#define ALIGNED 0x20


/**
 * An array for the number of blocksizes is allocated. This constant
 * defines its size. It is set on 32 as we won't probably allocate
 * blocks of 2^32 bytes or more...
 */

#define NBR_BLOCKTYPES 32



/**
 * Module commandline parameter: An array is passed as parameter. A
 * positive number at index i of the array specified the number of
 * blocks of size 2^i bytes that are allocated in the system. The
 * array length is an element of {0, 1, 2, ..., NBR_BLOCKTYPES}.
 */



MODULE_PARM(blocks, "0-32i");
MODULE_PARM_DESC(blocks, "The desired block sizes");


//-------------------------------------------------------------------
// DATA STRUCTURES
//-------------------------------------------------------------------


/**
 * This struct is at the beginning of each memory block. 
 *
 * @param index specifies the queue of the blocktypes - array where this block
 * should be stored. 
 *
 * @param next points to the next block in the block list
 */

typedef struct mem_header_t_ {
  int index;
  int id;
  int size;
  struct mem_header_t_ *next;
}
mem_header_t;


/**
 * To allow for more than one phys_area_block
 */
typedef struct phys_area_t_ {
  struct phys_area_t_ *next;
  void *phys_area;
}
phys_area_t;


/**
 * For each block size there is one entry of block_entry_t in the
 * array blocklists. 
 */

typedef struct {
  mem_header_t* first;
  phys_area_t *first_phys_area;
  int phys_area_size;
  int element_size;
  pthread_mutex_t mutex;
  int blocks_avail;
}
block_entry_t;


int allocate_one_block( int block );


//-------------------------------------------------------------------
// GLOBAL VARIABLES
//-------------------------------------------------------------------


/**
 * The parameter "blocks" which are specified at load-time with insmod
 * can be retrieved in the following array "blocks".
 */

int blocks[NBR_BLOCKTYPES] = {
			      // 2^0 to 2^7
			      0, 0, 0, 0, 100, 0, 0, 2000,
			      // 2^8 to 2^15
                              1000, 1000, 0, 0, 100, 20, 100, 20,
			      // 2^16 to 2^23
                              100, 100, 2, 2, 0, 10, 2, 1,
			      // 2^24 to 2^31
			      // 16MB 32MB 64MB 128MB 256MB 512MB 1GB 2GB
                              1, 1, 0, 0, 0, 0, 0, 0};



/**
 * The size of the header when it is properly aligned. This is a
 * multiple of __alignof__(mem_header_t).
 */

int aligned_header_size_;



/**
 * The array blocklists is the central datastructure in this
 * module. Every entry manages one list of memory blocks, each one
 * with a mutex and its own continuous memory segment. 
 */

block_entry_t blocklists[NBR_BLOCKTYPES];


//-------------------------------------------------------------------
// INTERNAL FUNCTIONS
//-------------------------------------------------------------------


/**
 * This function finds for a given size the index of the blocklist
 * whose blocks are just enough big to hold a memory area of "size"
 * bytes. If size is bigger than the biggest block, -1 is returned i
 * order to report an error.
 *
 * @param size : the argument
 */

inline int get_blocklists_index(int size) {
  int pwr2 = 0;
  int index = MIN_BLOCK_PWR_2;

  // if size too big:
  if (size > (1 << MAX_BLOCK_PWR_2)) {
    PR_DBG(0, "Error: Can't allocate %i bytes, no blocklist with blocks of this size!\n",
           size);
    return -1;
  }
  // if size too small:
  if (size <= 0) {
    PR_DBG(0, "Error: Size 0 or negative\n");
    return -1;
  }

  // if everything ok, calculate index:
  for ( pwr2 = (1 << MIN_BLOCK_PWR_2);
        ( ( pwr2 < size ) || ( !blocklists[index].first_phys_area ) ) &&
        ( index <= MAX_BLOCK_PWR_2 );
        pwr2 <<= 1) {
    index++;
  }
  // Something went wrong
  if ( index > MAX_BLOCK_PWR_2 ) {
    PR_DBG(0, "Error: Can't allocate %i bytes, no blocklist with blocks of this size!\n", size);
    return -1;
  }
  return index;
}



/**
 * Get a block from the blocklist with index "index" in the
 * blocklists-array. If no block is available anymore, it tries to
 * fetch a new block and returns NULL if failed.
 *
 * @param index The index of the blocklist in the blocklists[] array.
 *
 * @return a pointer to a block or 0 in case of an error.
 */

mem_header_t *get_block(int index) {
  mem_header_t *block;
  if (index < 0 || index >= NBR_BLOCKTYPES) {
    PR_DBG(0, "get_block: index %i invalid!!!", index);
    return 0;
  }

  pthread_mutex_lock(&blocklists[index].mutex);
  if (blocklists[index].first_phys_area) {
    if ( blocklists[index].blocks_avail == 0 ) {
      if ( allocate_one_block( index ) ) {
        PR_DBG( 0, "Couldn't add memory to block %i.\n",
                index );
        return NULL;
      }
      PR_DBG( 2, "Added some more memory to block %i\n", index );
    }
    block = blocklists[index].first;
    blocklists[index].first = blocklists[index].first->next;
    blocklists[index].blocks_avail--;
  } else {
    PR_DBG( 0, "Tried to get an unitialised block. Really weird\n" );
    return NULL;
  }
  pthread_mutex_unlock(&blocklists[index].mutex);
  block->id = BLOCK_USED;
  return block;
}



/**
 * Create linked list on a specified continuous segment. A pointer to
 * the first element is returned. The last element points to 0 and can
 * be recognized by this property.
 *
 * @param segment A pointer to the unformatted memory segment
 *
 * @param element_size The size of the elements of the list. This must
 * be the space which is used when the elements are properly aligned.
 *
 * @nbr_elements The number of elements which should be allocated.
 *
 * @index The number which should be put into the index field of a
 * memory header. This is used by the swr_free() routine to assign a
 * freed block to the right list.
 * 
 * @return A pointer to the first element of the list
 */

mem_header_t *format_segment(void *segment,
                             int element_size,
                             int nbr_elements,
                             int index) {
  mem_header_t *block;
  void *ptr;
  int i;
  // initialize the two pointers
  ptr = segment;
  block = (mem_header_t *)ptr;

  for (i = 0; i < nbr_elements - 1; i++) {
    ptr += element_size;
    block->next = (mem_header_t *)ptr;
    block->index = index;
    block->id = BLOCK_FREE;
    block = block->next;
  }
  // the last element points to 0
  block->next = 0;
  block->index = index;
  // return pointer to first
  return (mem_header_t *)segment;
}



/**
 * Wrapper for the allocation function of the bigphysarea
 * patch. Returns 0 when an error occurs.
 *
 * @param size in bytes
 *
 * @return A pointer to the physical area or 0 in case of an error.
 */

void *phys_malloc(int size) {
  void *address;
  int pages = (size + PAGE_SIZE - 1)/PAGE_SIZE;
  if (!(address = bigphysarea_alloc_pages(pages, 1, GFP_KERNEL))) {
    PR_DBG(0, "phys_malloc: Couldn't allocate physical memory block\n");
  }
  return address;
}



/**
 * Wrapper for the free function of the bigphysarea patch.
 */
void phys_free(void *address) {
  if (address) {
    bigphysarea_free_pages(address);
  }
}



/**
 * Initialize blocklists array, set pointers to 0 etc.
 */

void initialize_blocklists_array( void ) {