lnet/doc/Data-structures

   1 In this document I will try to draw the data structures and how they
   2 interrelate in the Portals 3 reference implementation.  It is probably
   3 best shown with a drawing, so there may be an additional xfig or
   4 Postscript figure.
   5
   6
   7 MEMORY POOLS:
   8 ------------
   9
  10 First, a digression on memory allocation in the library.  As mentioned
  11 in the NAL Writer's Guide, the library does not link against any
  12 standard C libraries and as such is unable to dynamically allocate
  13 memory on its own.  It requires that the NAL implement a method
  14 for allocation that is appropriate for the protection domain in
  15 which the library lives.  This is only called when a network
  16 interface is initialized to allocate the Portals object pools.
  17
  18 These pools are preallocate blocks of objects that the library
  19 can rapidly make active and manage with a minimum of overhead.
  20 It is also cuts down on overhead for setting up structures
  21 since the NAL->malloc() callback does not need to be called
  22 for each object.
  23
  24 The objects are maintained on a per-object type singly linked free
  25 list and contain a pointer to the next free object.  This pointer
  26 is NULL if the object is not on the free list and is non-zero
  27 if it is on the list.  The special sentinal value of 0xDEADBEEF
  28 is used to mark the end of the free list since NULL could
  29 indicate that the last object in the list is not free.
  30
  31 When one of the lib_*_alloc() functions is called, the library
  32 returns the head of the free list and advances the head pointer
  33 to the next item on the list.  The special case of 0xDEADBEEF is
  34 checked and a NULL pointer is returned if there are no more
  35 objects of this type available.   The lib_*_free() functions
  36 are even simpler -- check to ensure that the object is not already
  37 free, set its next pointer to the current head and then set
  38 the head to be this newly freed object.
  39
  40 Since C does not have templates, I did the next best thing and wrote
  41 the memory pool allocation code as a macro that expands based on the
  42 type of the argument.  The mk_alloc(T) macro expands to
  43 write the _lib_T_alloc() and lib_T_free() functions.
  44 It requires that the object have a pointer of the type T named
  45 "next_free".  There are also functions that map _lib_T_alloc()
  46 to lib_T_alloc() so that the library can add some extra
  47 functionality to the T constructor.
  48
  49
  50
  51 LINKED LISTS:
  52 ------------
  53
  54 Many of the active Portals objects are stored in doubly linked lists
  55 when they are active.  These are always implemented with the pointer
  56 to the next object and a pointer to the next pointer of the
  57 previous object.  This avoids the "dummy head" object or
  58 special cases for inserting at the beginning or end of the list.
  59 The pointer manipulations are a little hairy at times, but
  60 I hope that they are understandable.
  61
  62 The actual linked list code is implemented as macros in <lib-p30.h>,
  63 although the object has to know about
  64
  65