doc/libacl.txt

   1 Internals of the libacl library
   2 ===============================
   3
   4 Posix 1003.1e DS17 leaves the library developer relatively few choices
   5 on how to  implement the  library. A  pseudo object  oriented approach
   6 seems necessary (otherwise, not all of the  requirements can  be met).
   7 Unfortunately, C is no object oriented language,  so the  classes etc.
   8 need to be hand coded. Here is how it works.
   9
  10 From the user's point of view, the following things are objects:
  11
  12   F - acl_t objects
  13     - acl_entry_t objects
  14     - acl_permset_t objects
  15   F - strings returned by acl_to_text
  16   F - entities returned by acl_get_qualifier
  17
  18 The objects flagged with F need to be freed with acl_free()  when they
  19 are no longer needed.
  20
  21 The user gets pointers to the contents of  these objects.  Each object
  22 also has a prefix, which is not accessible from the user. The complete
  23 objects  are  declared  in  <lib/libacl.h>. The  p_magic field  of the
  24 prefix is set to <object_name>_MAGIC.
  25
  26 The macros ext2int() and  int2ext() convert  between the  internal and
  27 external view on objects. The  macros new_obj_p()  and new_var_obj_p()
  28 create a new object and object with  variable size,  respectively. See
  29 the code for the rest.
  30
  31 The code necessary to access fields in objects, especially  in objects
  32 accessed through indirections, would get almost unreadable. The second
  33 ACL entry of an ACL would be:
  34
  35   acl_obj *acl_p;
  36   acl_entry_obj *acl_entry_p = acl_p->i.a_ring->i.e_next;
  37
  38 For  better  readability,  all the  "i.a_", "i.e_"  etc. parts  can be
  39 hidden using macros:
  40
  41   acl_obj *acl_p;
  42   acl_entry_obj *acl_entry_p = acl_p->aring->enext;
  43
  44
  45 ACLs and ACL entries
  46 ====================
  47 The ACL entries associated with an ACL are stored  on a  sorted double
  48 linked list. The first and last entries in that list are available via
  49 ACL object. This is implemented with a little trick:
  50
  51   The  acl_obj  and  acl_entry_obj  have  {a,e}_prev  and {a,e}_prev
  52   pointers at the same  memory location  (directly after  the object
  53   prefix).  The  a_prev  and  a_next  entries  of  an   acl_obj  are
  54   initialized to point to the acl_obj itself  (this requires  a type
  55   cast).  We  only  need  to check  if the  acl_obj object  has been
  56   reached to detect the end of  the list.  Since the  acl_obj object
  57   isn't actually an acl_entry_obj object, care must be taken  not to
  58   manipulate any of the other acl_entry_obj fields other than e_prev
  59   and e_next.
  60
  61 Whenever  an  entry  is  changed,  __acl_reorder_obj_p()  reorders the
  62 entries  accordingly. This  takes O(n^2)  time, but  that's not  a big
  63 problem as long as ACLs don't contain very many  entries. Some  of the
  64 library  functions  need a  sorted ACL  anyway, so  the best  we could
  65 possibly do is  O(n*log(n)), with  a sorted  flag in  each ACL,  and a
  66 complicated  sorting  function  (the  linked  list  would  have  to be
  67 converted to an array first to allow more efficient sorting).
  68
  69
  70 Hope that helps. Good luck!
  71
  72 Andreas
  73