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