Internals of the libacl library

===============================

Posix 1003.1e DS17 leaves the library developer relatively few choices

on how to  implement the  library. A  pseudo object  oriented approach

seems necessary (otherwise, not all of the  requirements can  be met).

Unfortunately, C is no object oriented language,  so the  classes etc.

need to be hand coded. Here is how it works. 

From the user's point of view, the following things are objects:

  F - acl_t objects

    - acl_entry_t objects

    - acl_permset_t objects

  F - strings returned by acl_to_text

  F - entities returned by acl_get_qualifier

The objects flagged with F need to be freed with acl_free()  when they

are no longer needed. 

The user gets pointers to the contents of  these objects.  Each object

also has a prefix, which is not accessible from the user. The complete

objects  are  declared  in  <lib/libacl.h>. The  p_magic field  of the

prefix is set to <object_name>_MAGIC. 

The macros ext2int() and  int2ext() convert  between the  internal and

external view on objects. The  macros new_obj_p()  and new_var_obj_p()

create a new object and object with  variable size,  respectively. See

the code for the rest. 

The code necessary to access fields in objects, especially  in objects

accessed through indirections, would get almost unreadable. The second

ACL entry of an ACL would be: 

  acl_obj *acl_p;

  acl_entry_obj *acl_entry_p = acl_p->i.a_ring->i.e_next;

For  better  readability,  all the  "i.a_", "i.e_"  etc. parts  can be

hidden using macros: 

  acl_obj *acl_p;

  acl_entry_obj *acl_entry_p = acl_p->aring->enext;

ACLs and ACL entries

====================

The ACL entries associated with an ACL are stored  on a  sorted double

linked list. The first and last entries in that list are available via

ACL object. This is implemented with a little trick: 

  The  acl_obj  and  acl_entry_obj  have  {a,e}_prev  and {a,e}_prev

  pointers at the same  memory location  (directly after  the object

  prefix).  The  a_prev  and  a_next  entries  of  an   acl_obj  are

  initialized to point to the acl_obj itself  (this requires  a type

  cast).  We  only  need  to check  if the  acl_obj object  has been

  reached to detect the end of  the list.  Since the  acl_obj object

  isn't actually an acl_entry_obj object, care must be taken  not to

  manipulate any of the other acl_entry_obj fields other than e_prev

  and e_next. 

Whenever  an  entry  is  changed,  __acl_reorder_obj_p()  reorders the

entries  accordingly. This  takes O(n^2)  time, but  that's not  a big

problem as long as ACLs don't contain very many  entries. Some  of the

library  functions  need a  sorted ACL  anyway, so  the best  we could

possibly do is  O(n*log(n)), with  a sorted  flag in  each ACL,  and a

complicated  sorting  function  (the  linked  list  would  have  to be

converted to an array first to allow more efficient sorting). 

Hope that helps. Good luck!

Andreas