ipc/shm_fragment.c

   1 /***************************************************************************
   2  * Copyright 1995, Technion, Israel Institute of Technology
   3  * Electrical Eng, Software Lab.
   4  * Author:    Michael Veksler.
   5  ***************************************************************************
   6  * File:      shm_fragment.c
   7  * Purpose:   Data fragments and free list items. Allocate and free blocks.
   8  ***************************************************************************
   9  */
  10 #ifdef CONFIG_IPC
  11
  12 #include <stdio.h>                 /* for debugging only */
  13 #include <debug.h>                 /* for "stddeb" */
  14
  15 #include "shm_fragment.h"
  16 #include "shm_block.h"
  17
  18 /******************************************************************************
  19  *
  20  * Free list: all fragments are ordered according to memory location.
  21  *            new fragments are inserted in this way.
  22  *
  23  ******************************************************************************
  24  */
  25
  26 #define FRAG_PTR(block,ofs) ((struct shm_fragment *) ((char *) block + ofs) )
  27 #define NEXT_FRAG(block,ofs) ( FRAG_PTR(block,ofs)->info.next )
  28
  29 /* setup first item in the free list */
  30 void shm_FragmentInit(struct shm_block *block,int first, int size)
  31 {
  32   struct shm_fragment *fragment;
  33
  34   /* round up to nearest 16 byte boundary */
  35   first=(first+15)& ~15;
  36   block->free_list=first;
  37
  38   /* make all the block (exluding the header) free */
  39   fragment= FRAG_PTR(block, first);
  40   block->free=  fragment->size=  size-first;
  41   fragment->info.next=0;
  42 }
  43
  44 void shm_FragPtrFree(struct shm_block *block, void *ptr)
  45 {
  46   /* ptr points to fragment->info.data, find pointer to fragment,
  47    * find the offset of this pointer in block.
  48    */
  49   if (ptr)
  50      shm_FragmentFree(block, PTR2REL(block, ptr));
  51 }
  52 void shm_FragmentFree(struct shm_block *block, int fragment_ofs)
  53 {
  54   struct shm_fragment *fragment=NULL;
  55   int prev;
  56   int next;
  57
  58   fragment_ofs-=(int )&fragment->info.data;
  59   fragment= FRAG_PTR(block, fragment_ofs);
  60
  61   block->free+=fragment->size;
  62   /* scan free list to find candidates for merging with fragment */
  63   for (prev=0, next=block->free_list;
  64        (next!=0) && (fragment_ofs > next)  ;
  65        prev=next, next=NEXT_FRAG(block,next) )
  66      ;
  67
  68   /* insert fragment between, prev and next
  69    *  prev==0: fragment will be the first item in free list
  70    *  next==0: fragment will be the last item in free list
  71    */
  72
  73
  74   /* update fragment (point to next, or merge with next) */
  75
  76   if ( fragment_ofs+fragment->size == next ) {
  77      /* merge with the next free block */
  78      fragment->size+=    FRAG_PTR(block,next)->size;
  79      fragment->info.next=FRAG_PTR(block,next)->info.next;
  80   } else
  81      /* fragment should be inserted before the next fragment or end of */
  82      /* list. (not merged)  */
  83      fragment->info.next=next;
  84   /* now fragment has all the information about the rest of the list */
  85
  86
  87   /* upate prev fragment (point or merge with fragment) */
  88
  89   if (prev==0)             /* first item in free list */
  90      block->free_list=fragment_ofs;
  91   else if ( prev+FRAG_PTR(block,prev)->size == fragment_ofs ) {
  92      /* merge fragment with previous fragment */
  93      FRAG_PTR(block,prev)->size+=    fragment->size;
  94      FRAG_PTR(block,prev)->info.next=fragment->info.next;
  95   } else
  96      /* insert fragment after previous fragment */
  97      FRAG_PTR(block,prev)->info.next=fragment_ofs;
  98 }
  99
 100 /* use "first fit" algorithm,
 101  * return: offset to data in fragment.
 102  */
 103 int shm_FragmentAlloc(struct shm_block *block, int size)
 104 {
 105   int prev;
 106   int candidate;
 107   struct shm_fragment *fragment;
 108   struct shm_fragment *ret_fragment;
 109
 110   if (size <= 0)
 111      return NIL;
 112   /* add size of  "fragment->size" */
 113   size+= (char *)&fragment->info.data - (char *)fragment ;
 114
 115   /* round "size" to nearest 16 byte value */
 116   size= (size+15) & ~15;
 117   if (size > block->free)
 118      return NIL;
 119   /* scan free list to find candidates for allocation */
 120   for (prev=0, candidate=block->free_list;
 121        candidate!=0 ;
 122        prev=candidate, candidate= fragment->info.next )
 123   {
 124      fragment=FRAG_PTR(block,candidate);
 125      if (fragment->size >= size)
 126         break;
 127   }
 128
 129   if (candidate == 0)
 130      return NIL;
 131
 132   block->free-=size;
 133   if (fragment->size == size) {
 134      if (prev == 0)
 135         block->free_list= fragment->info.next;
 136      else
 137         FRAG_PTR(block,prev)->info.next= fragment->info.next;
 138      return PTR2REL(block, &fragment->info.data);
 139   }
 140
 141   /* fragment->size > size */
 142
 143   /* Split fragment in two, return one part, put the other in free list.  */
 144   /* The part that starts at the old location - will stay in the free list. */
 145   fragment->size -= size;
 146
 147   ret_fragment=FRAG_PTR(block, candidate + fragment->size);
 148   ret_fragment->size= size;
 149   return PTR2REL(block, ret_fragment->info.data);
 150 }
 151
 152 /* like shm_FragmentAlloc, returns pointer instead of offset */
 153 char *shm_FragPtrAlloc(struct shm_block *block, int size)
 154 {
 155   int ofs;
 156   ofs= shm_FragmentAlloc(block,size);
 157   if (ofs == NIL)
 158      return NULL;
 159   else
 160      return (char *) REL2PTR(block, ofs);
 161 }
 162 /* This is used for debugging only */
 163 void shm_print_free_list(struct shm_block *block)
 164 {
 165   struct shm_fragment *fragment;
 166   int item;
 167
 168   item=block->free_list;
 169   if (item==0) {
 170      DUMP("no free fragments");
 171   } else {
 172      for (; item ; item=fragment->info.next) {
 173         fragment=FRAG_PTR(block,item);
 174         DUMP("{0x%04x,0x%04x} ",item,fragment->size);
 175      }
 176   }
 177   DUMP(" [total free=%04x]\n",block->free);
 178   fflush(stddeb);
 179 }
 180
 181 #endif  /* CONFIG_IPC */