diff options
author | Michael Stone <michael@laptop.org> | 2009-12-09 05:15:49 (GMT) |
---|---|---|
committer | Michael Stone <michael@laptop.org> | 2009-12-10 02:24:49 (GMT) |
commit | 9babd2f652bd5b06206f8fc43e2403cd09cc7038 (patch) | |
tree | 751c42c83ded89f6b736f4c1752a4b424cba74a8 | |
parent | 38bb9be39486214eeb7e0f4273fa0051ed880adc (diff) |
Add a novel singly-linked list implementation.
-rw-r--r-- | rainbow/nss/Makefile | 11 | ||||
-rw-r--r-- | rainbow/nss/cgen.h | 2 | ||||
-rw-r--r-- | rainbow/nss/list.h | 517 | ||||
-rw-r--r-- | rainbow/nss/nss-rainbow.c | 176 | ||||
-rw-r--r-- | rainbow/nss/slist.c | 32 | ||||
-rw-r--r-- | rainbow/nss/slist.h | 50 | ||||
-rw-r--r-- | rainbow/nss/test_slist.c | 45 |
7 files changed, 238 insertions, 595 deletions
diff --git a/rainbow/nss/Makefile b/rainbow/nss/Makefile index 056b5e7..6fe8dcf 100644 --- a/rainbow/nss/Makefile +++ b/rainbow/nss/Makefile @@ -9,16 +9,18 @@ WARNFLAGS = \ # Compiler flags for generating dependencies DEPFLAGS = -MMD -MP CFLAGS ?= -O3 +#CFLAGS ?= -O2 -g ALLCFLAGS = -std=gnu99 -fPIC $(WARNFLAGS) $(DEPFLAGS) $(CFLAGS) # declarations -RAINBOW_OBJS = nss-rainbow.o buf.o nat.o +RAINBOW_OBJS = nss-rainbow.o buf.o nat.o slist.o UIDS_OBJS = uids.o GIDS_OBJS = gids.o +TEST_SLIST_OBJS = test_slist.o slist.o TEST_NAT_OBJS = test_nat.o nat.o -ALL_OBJS = $(RAINBOW_OBJS) $(UIDS_OBJS) $(GIDS_OBJS) $(TEST_NAT_OBJS) -BINARIES = libnss_rainbow.so.2 uids gids test_nat +ALL_OBJS = $(RAINBOW_OBJS) $(UIDS_OBJS) $(GIDS_OBJS) $(TEST_SLIST_OBJS) $(TEST_NAT_OBJS) +BINARIES = libnss_rainbow.so.2 uids gids test_slist test_nat # targets @@ -38,6 +40,9 @@ install: # linked binaries +test_slist: $(TEST_SLIST_OBJS) + $(CC) $(ALLCFLAGS) -o $@ $^ + test_nat: $(TEST_NAT_OBJS) $(CC) $(ALLCFLAGS) -o $@ $^ diff --git a/rainbow/nss/cgen.h b/rainbow/nss/cgen.h index 81bc895..cd5a275 100644 --- a/rainbow/nss/cgen.h +++ b/rainbow/nss/cgen.h @@ -1,7 +1,7 @@ #define STATIC_ASSERT(expr) extern char __static_assertion_failed [(expr) ? 1 : -1] #define SAVE_ERR(EXPR) {int __errno_save = errno; EXPR; errno = __errno_save;} #define __XSTRING(X) __STRING(X) -/* #define PERROR(msg) {int __errno_cache = errno; if (getenv(DEBUG) != NULL) {dprintf(2, "%s|%d| %s: %s\n", __FILE__, __LINE__, __func__, msg); if (__errno_cache) {dprintf(2, "Error %d: %s\n", __errno_cache, strerror(__errno_cache));}};} */ +/* #define PERROR(msg) {int __errno_cache = errno; if (getenv(DEBUG) != NULL) {fprintf(stderr, "%s|%d| %s: %s\n", __FILE__, __LINE__, __func__, msg); if (__errno_cache) {fprintf(stderr, "Error %d: %s\n", __errno_cache, strerror(__errno_cache));}};} */ #define PERROR(msg) #define CHK(EXPR, MSG, ERR_LABEL) {if(EXPR) { PERROR(MSG); goto ERR_LABEL;}} #define LET(LETEXPR, CONDEXPR, MSG, ERR_LABEL) LETEXPR; if (CONDEXPR) { PERROR(MSG); goto ERR_LABEL;} diff --git a/rainbow/nss/list.h b/rainbow/nss/list.h deleted file mode 100644 index 81ad31e..0000000 --- a/rainbow/nss/list.h +++ /dev/null @@ -1,517 +0,0 @@ -/** - * - * I grub it from linux kernel source code and fix it for user space - * program. Of course, this is a GPL licensed header file. - * - * Here is a recipe to cook list.h for user space program - * - * 1. copy list.h from linux/include/list.h - * 2. remove - * - #ifdef __KERNE__ and its #endif - * - all #include line - * - prefetch() and rcu related functions - * 3. add macro offsetof() and container_of - * - * - kazutomo@mcs.anl.gov - */ -#ifndef _LINUX_LIST_H -#define _LINUX_LIST_H - -/** - * @name from other kernel headers - */ -/*@{*/ - -/** - * Get offset of a member - */ -#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) - -/** - * Casts a member of a structure out to the containing structure - * @param ptr the pointer to the member. - * @param type the type of the container struct this is embedded in. - * @param member the name of the member within the struct. - * - */ -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) -/*@}*/ - - -/* - * These are non-NULL pointers that will result in page faults - * under normal circumstances, used to verify that nobody uses - * non-initialized list entries. - */ -#define LIST_POISON1 ((void *) 0x00100100) -#define LIST_POISON2 ((void *) 0x00200200) - -/** - * Simple doubly linked list implementation. - * - * Some of the internal functions ("__xxx") are useful when - * manipulating whole lists rather than single entries, as - * sometimes we already know the next/prev entries and we can - * generate better code by using them directly rather than - * using the generic single-entry routines. - */ -struct list_head { - struct list_head *next, *prev; -}; - -#define LIST_HEAD_INIT(name) { &(name), &(name) } - -#define LIST_HEAD(name) \ - struct list_head name = LIST_HEAD_INIT(name) - -#define INIT_LIST_HEAD(ptr) do { \ - (ptr)->next = (ptr); (ptr)->prev = (ptr); \ -} while (0) - -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_add(struct list_head *new, - struct list_head *prev, - struct list_head *next) -{ - next->prev = new; - new->next = next; - new->prev = prev; - prev->next = new; -} - -/** - * list_add - add a new entry - * @new: new entry to be added - * @head: list head to add it after - * - * Insert a new entry after the specified head. - * This is good for implementing stacks. - */ -static inline void list_add(struct list_head *new, struct list_head *head) -{ - __list_add(new, head, head->next); -} - -/** - * list_add_tail - add a new entry - * @new: new entry to be added - * @head: list head to add it before - * - * Insert a new entry before the specified head. - * This is useful for implementing queues. - */ -static inline void list_add_tail(struct list_head *new, struct list_head *head) -{ - __list_add(new, head->prev, head); -} - - -/* - * Delete a list entry by making the prev/next entries - * point to each other. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_del(struct list_head * prev, struct list_head * next) -{ - next->prev = prev; - prev->next = next; -} - -/** - * list_del - deletes entry from list. - * @entry: the element to delete from the list. - * Note: list_empty on entry does not return true after this, the entry is - * in an undefined state. - */ -static inline void list_del(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - entry->next = LIST_POISON1; - entry->prev = LIST_POISON2; -} - - - -/** - * list_del_init - deletes entry from list and reinitialize it. - * @entry: the element to delete from the list. - */ -static inline void list_del_init(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - INIT_LIST_HEAD(entry); -} - -/** - * list_move - delete from one list and add as another's head - * @list: the entry to move - * @head: the head that will precede our entry - */ -static inline void list_move(struct list_head *list, struct list_head *head) -{ - __list_del(list->prev, list->next); - list_add(list, head); -} - -/** - * list_move_tail - delete from one list and add as another's tail - * @list: the entry to move - * @head: the head that will follow our entry - */ -static inline void list_move_tail(struct list_head *list, - struct list_head *head) -{ - __list_del(list->prev, list->next); - list_add_tail(list, head); -} - -/** - * list_empty - tests whether a list is empty - * @head: the list to test. - */ -static inline int list_empty(const struct list_head *head) -{ - return head->next == head; -} - -static inline void __list_splice(struct list_head *list, - struct list_head *head) -{ - struct list_head *first = list->next; - struct list_head *last = list->prev; - struct list_head *at = head->next; - - first->prev = head; - head->next = first; - - last->next = at; - at->prev = last; -} - -/** - * list_splice - join two lists - * @list: the new list to add. - * @head: the place to add it in the first list. - */ -static inline void list_splice(struct list_head *list, struct list_head *head) -{ - if (!list_empty(list)) - __list_splice(list, head); -} - -/** - * list_splice_init - join two lists and reinitialise the emptied list. - * @list: the new list to add. - * @head: the place to add it in the first list. - * - * The list at @list is reinitialised - */ -static inline void list_splice_init(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) { - __list_splice(list, head); - INIT_LIST_HEAD(list); - } -} - -/** - * list_entry - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - */ -#define list_entry(ptr, type, member) \ - container_of(ptr, type, member) - -/** - * list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. - */ - -#define list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); \ - pos = pos->next) - -/** - * __list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. - * - * This variant differs from list_for_each() in that it's the - * simplest possible list iteration code, no prefetching is done. - * Use this for code that knows the list to be very short (empty - * or 1 entry) most of the time. - */ -#define __list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) - -/** - * list_for_each_prev - iterate over a list backwards - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. - */ -#define list_for_each_prev(pos, head) \ - for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ - pos = pos->prev) - -/** - * list_for_each_safe - iterate over a list safe against removal of list entry - * @pos: the &struct list_head to use as a loop counter. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_safe(pos, n, head) \ - for (pos = (head)->next, n = pos->next; pos != (head); \ - pos = n, n = pos->next) - -/** - * list_for_each_entry - iterate over list of given type - * @pos: the type * to use as a loop counter. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry(pos, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_reverse - iterate backwards over list of given type. - * @pos: the type * to use as a loop counter. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_reverse(pos, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.prev, typeof(*pos), member)) - -/** - * list_prepare_entry - prepare a pos entry for use as a start point in - * list_for_each_entry_continue - * @pos: the type * to use as a start point - * @head: the head of the list - * @member: the name of the list_struct within the struct. - */ -#define list_prepare_entry(pos, head, member) \ - ((pos) ? : list_entry(head, typeof(*pos), member)) - -/** - * list_for_each_entry_continue - iterate over list of given type - * continuing after existing point - * @pos: the type * to use as a loop counter. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_continue(pos, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @pos: the type * to use as a loop counter. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_safe(pos, n, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_continue - iterate over list of given type - * continuing after existing point safe against removal of list entry - * @pos: the type * to use as a loop counter. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_safe_continue(pos, n, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against - * removal of list entry - * @pos: the type * to use as a loop counter. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_safe_reverse(pos, n, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member), \ - n = list_entry(pos->member.prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.prev, typeof(*n), member)) - - - - -/* - * Double linked lists with a single pointer list head. - * Mostly useful for hash tables where the two pointer list head is - * too wasteful. - * You lose the ability to access the tail in O(1). - */ - -struct hlist_head { - struct hlist_node *first; -}; - -struct hlist_node { - struct hlist_node *next, **pprev; -}; - -#define HLIST_HEAD_INIT { .first = NULL } -#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } -#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) -#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL) - -static inline int hlist_unhashed(const struct hlist_node *h) -{ - return !h->pprev; -} - -static inline int hlist_empty(const struct hlist_head *h) -{ - return !h->first; -} - -static inline void __hlist_del(struct hlist_node *n) -{ - struct hlist_node *next = n->next; - struct hlist_node **pprev = n->pprev; - *pprev = next; - if (next) - next->pprev = pprev; -} - -static inline void hlist_del(struct hlist_node *n) -{ - __hlist_del(n); - n->next = LIST_POISON1; - n->pprev = LIST_POISON2; -} - - -static inline void hlist_del_init(struct hlist_node *n) -{ - if (n->pprev) { - __hlist_del(n); - INIT_HLIST_NODE(n); - } -} - -static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) -{ - struct hlist_node *first = h->first; - n->next = first; - if (first) - first->pprev = &n->next; - h->first = n; - n->pprev = &h->first; -} - - - -/* next must be != NULL */ -static inline void hlist_add_before(struct hlist_node *n, - struct hlist_node *next) -{ - n->pprev = next->pprev; - n->next = next; - next->pprev = &n->next; - *(n->pprev) = n; -} - -static inline void hlist_add_after(struct hlist_node *n, - struct hlist_node *next) -{ - next->next = n->next; - n->next = next; - next->pprev = &n->next; - - if(next->next) - next->next->pprev = &next->next; -} - - - -#define hlist_entry(ptr, type, member) container_of(ptr,type,member) - -#define hlist_for_each(pos, head) \ - for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ - pos = pos->next) - -#define hlist_for_each_safe(pos, n, head) \ - for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ - pos = n) - -/** - * hlist_for_each_entry - iterate over list of given type - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @head: the head for your list. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry(tpos, pos, head, member) \ - for (pos = (head)->first; \ - pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_continue(tpos, pos, member) \ - for (pos = (pos)->next; \ - pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_from - iterate over a hlist continuing from existing point - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_from(tpos, pos, member) \ - for (; pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @n: another &struct hlist_node to use as temporary storage - * @head: the head for your list. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ - for (pos = (head)->first; \ - pos && ({ n = pos->next; 1; }) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = n) - - -#endif diff --git a/rainbow/nss/nss-rainbow.c b/rainbow/nss/nss-rainbow.c index de6be89..1f69ac3 100644 --- a/rainbow/nss/nss-rainbow.c +++ b/rainbow/nss/nss-rainbow.c @@ -20,7 +20,7 @@ #include "buf.h" #include "nat.h" -#include "list.h" +#include "slist.h" /* constants */ #include "config/shell.h" @@ -62,6 +62,16 @@ out_error_spool: return NSS_STATUS_UNAVAIL; } +int check_gid_in_range(gid_t gid) +{ + TST(gid < 10000 || gid > 60000, errno = ENOENT, + "Gid outside [10000, 60000].", out_error); + return 0; +out_error: + return 1; +} + + int read_gid_for_uid(unsigned long uid, unsigned long* gid) { char gid_path[NAME_MAX+1]; @@ -191,19 +201,33 @@ out_error_name: return NSS_STATUS_NOTFOUND; } -struct member_list { - struct list_head list; +struct member_row { + struct slist list; char* name; }; - -struct gid_list { - struct list_head list; - struct member_list members; +struct gid_row { + struct slist list; + struct member_row *members; gid_t gid; }; -struct gid_list g_gids; -struct gid_list* g_gid; +struct gid_row* g_gids; +struct gid_row* g_cur_gid; + +void member_row_init(struct member_row* self) { + self->name = NULL; + slist_init(&self->list); +} + +void gid_row_init(struct gid_row* self) { + slist_init(&self->list); + self->members = NULL; + self->gid = -1; +} + +void gid_row_add_member(struct gid_row* self, struct member_row* mr) { + slist_extend(&self->members->list, &mr->list); +} int members_scanner(const struct dirent* d) { size_t member_len = strlen(d->d_name); @@ -214,17 +238,22 @@ int members_scanner(const struct dirent* d) { || (member_len == 2 && d->d_name[0] == '.' && d->d_name[1] == '.'), "Invalid data-gid-to-member member path.", exit); - /* g_gid now points to the appropriate gid_list node. + /* g_cur_gid now points to the appropriate gid_row node. * There's no way that we could already have our current (uid, gid) row. * I think. :) * Therefore, we'll immediately insert it. */ - struct member_list* member_iter; - LET(member_iter = calloc(1, sizeof(struct member_list)), !member_iter, - "Unable to allocate new member_list node.", exit); - LET(member_iter->name = malloc(member_len+1), !member_iter->name, - "Unable to allocate new member_list->name.", exit); - strncpy(member_iter->name, member_str, member_len+1); - list_add_tail(&(member_iter->list), &(g_gid->members.list)); + struct member_row* mr; + + LET(mr = calloc(1, sizeof(struct member_row)), !mr, + "Unable to allocate new member_row node.", exit); + member_row_init(mr); + + LET(mr->name = malloc(member_len+1), !mr->name, + "Unable to allocate new member_row->name.", exit); + strncpy(mr->name, member_str, member_len+1); + + gid_row_add_member(g_cur_gid, mr); + exit: return 0; } @@ -236,6 +265,8 @@ gid_to_members_scanner(const struct dirent* d) { char path[NAME_MAX+1]; size_t path_len = NAME_MAX + 1; char* path_str = path; + struct gid_row* gr; + CHK(path_len == 0 || (path_len == 1 && d->d_name[0] == '.') @@ -250,27 +281,28 @@ gid_to_members_scanner(const struct dirent* d) { CHK(format_buf(&path_str, &path_len, SPOOL "/gid_to_members/%d", gid) == 1, "Unable to calculate data-gid-to-members path.", exit); - /* We might have already allocated a gid_list for our gid. + /* We might have already allocated a gid_row for our gid. * Therefore, search for it. */ - struct gid_list* gid_iter = NULL; - list_for_each_entry(gid_iter, &g_gids.list, list) { - if (gid_iter->gid == gid) { - g_gid = gid_iter; - break; - } + bool find_gid(struct gid_row* iter) { + if (iter->gid == gid) { g_cur_gid = iter; return 0; } else return 1; } + slist_search(struct gid_row, list, g_gids, found, not_found, &find_gid); - /* If we find no gid_list, make one and insert it. */ - if (&gid_iter->list == &g_gids.list) { - LET(gid_iter = malloc(sizeof(struct gid_list)), !gid_iter, - "Unable to allocate new gid_list node.", exit); - gid_iter->gid = gid; - INIT_LIST_HEAD(&(gid_iter->members.list)); - list_add_tail(&(gid_iter->list), &g_gids.list); - g_gid = gid_iter; - } +not_found: + LET(gr = calloc(1, sizeof(struct gid_row)), !gr, + "Unable to allocate new gid_row node.", exit); + gid_row_init(gr); + gr->gid = gid; + + LET(gr->members = calloc(1, sizeof(struct member_row)), !gr->members, + "Unable to allocate new gid_row->members node.", exit); + member_row_init(gr->members); + + slist_extend(&g_gids->list, &gr->list); + g_cur_gid = gr; - /* g_gid now points to an appropriate gid_list for us to fill in. */ +found: + /* g_cur_gid now points to an appropriate gid_row for us to fill in. */ CHK(scandir(path, &ents, members_scanner, versionsort) == -1, "Unable to scan members dir from $RAINBOW_SPOOL/gid_to_members/$GID.", exit); exit: @@ -279,31 +311,29 @@ exit: enum nss_status _nss_rainbow_setgrent(void) { struct dirent** ents; - INIT_LIST_HEAD(&g_gids.list); - INIT_LIST_HEAD(&g_gids.members.list); - g_gid = &g_gids; + LET(g_gids = calloc(1, sizeof(struct gid_row)), !g_gids, + "Unable to allocate new g_gids node.", out_error); + gid_row_init(g_gids); CHK(scandir(SPOOL "/gid_to_members", &ents, gid_to_members_scanner, versionsort) == -1, "Unable to extract gid->members dirs from $RAINBOW_SPOOL.", out_error); - g_gid = list_entry(g_gids.list.next, struct gid_list, list); + + g_cur_gid = container_of(g_gids->list.next, struct gid_row, list); return NSS_STATUS_SUCCESS; out_error: return NSS_STATUS_UNAVAIL; } enum nss_status _nss_rainbow_endgrent(void) { - struct gid_list* gid_iter; - struct member_list* member_iter; - while(!list_empty(&g_gids.list)) { - gid_iter = list_entry(g_gids.list.next, struct gid_list, list); - while(!list_empty(&(gid_iter->members.list))) { - member_iter = list_entry(gid_iter->members.list.next, struct member_list, list); - list_del(&(member_iter->list)); + void free_gid(struct gid_row* gid_iter) { + void free_member(struct member_row* member_iter) { free(member_iter->name); free(member_iter); } - list_del(&(gid_iter->list)); + slist_for(struct member_row, list, gid_iter->members, &free_member); free(gid_iter); } + slist_for(struct gid_row, list, g_gids, &free_gid); + return NSS_STATUS_SUCCESS; } /* @@ -315,9 +345,19 @@ struct group char **gr_mem; }; */ +int fill_member(struct member_row* member_iter, struct group* result, char** buf, size_t* buflen, size_t* member_count) { + result->gr_mem[*member_count] = *buf; + CHK(format_buf(buf, buflen, "%s", member_iter->name) == 1, + "Unable to write a group member.", out_error); + *member_count += 1; + + return 0; +out_error: + return 1; +} int -fill_group(struct group* result, char* buf, size_t buflen, struct gid_list* gid_iter) { +fill_group(struct group* result, char* buf, size_t buflen, struct gid_row* gid_iter) { result->gr_gid = gid_iter->gid; result->gr_name = result->gr_passwd = buf; @@ -325,12 +365,9 @@ fill_group(struct group* result, char* buf, size_t buflen, struct gid_list* gid_ "Unable to calculate group name.", out_error); /* count the number of members */ - struct member_list* member_iter; - struct list_head* member_node_iter; size_t member_count = 0; - list_for_each(member_node_iter, &(gid_iter->members.list)) { - member_count++; - } + void count_member(struct member_row* iter) { member_count++; } + slist_for(struct member_row, list, gid_iter->members, &count_member); /* reserve space for the member-pointers */ size_t member_size = (member_count+1)* sizeof(char*); @@ -343,12 +380,8 @@ fill_group(struct group* result, char* buf, size_t buflen, struct gid_list* gid_ /* fill in the members and swing the pointers */ member_count = 0; - list_for_each_entry(member_iter, &(gid_iter->members.list), list) { - result->gr_mem[member_count] = buf; - CHK(format_buf(&buf, &buflen, "%s", member_iter->name) == 1, - "Unable to write a group member.", out_error); - member_count++; - } + slist_while(struct member_row, list, gid_iter->members, out_error, + &fill_member, result, &buf, &buflen, &member_count); return 0; @@ -358,12 +391,12 @@ out_error: enum nss_status _nss_rainbow_getgrent_r(struct group *result, char *buf, size_t buflen, int *errnop) { - if (&g_gid->list == &g_gids.list) + if (&g_cur_gid->list == &g_gids->list) return NSS_STATUS_NOTFOUND; - CHK(fill_group(result, buf, buflen, g_gid) == 1, + CHK(fill_group(result, buf, buflen, g_cur_gid) == 1, "Unable to fill in group struct.", out_error_errno); - g_gid = list_entry(g_gid->list.next, struct gid_list, list); + g_cur_gid = container_of(g_cur_gid->list.next, struct gid_row, list); return NSS_STATUS_SUCCESS; @@ -372,15 +405,6 @@ out_error_errno: return NSS_STATUS_TRYAGAIN; } -int check_gid_in_range(gid_t gid) -{ - TST(gid < 10000 || gid > 60000, errno = ENOENT, - "Gid outside [10000, 60000].", out_error); - return 0; -out_error: - return 1; -} - enum nss_status _nss_rainbow_getgrgid_r(gid_t gid, struct group *result, char *buf, size_t buflen, int *errnop) { /* Getting errno and the return code exactly right is a pain. @@ -402,12 +426,16 @@ _nss_rainbow_getgrgid_r(gid_t gid, struct group *result, char *buf, size_t bufle "Gid outside [10000, 60000].", out_error); /* look up group data */ - struct gid_list* gid_iter = NULL; - list_for_each_entry(gid_iter, &g_gids.list, list) { - if (gid_iter->gid == gid) break; + struct gid_row* gid_iter = NULL; + bool find_gid(struct gid_row* iter, struct gid_row** result) { + if (iter->gid == gid) { *result = iter; return 0; } else return 1; } - TST(&gid_iter->list == &g_gids.list, ret = NSS_STATUS_NOTFOUND, + slist_search(struct gid_row, list, g_gids, resume, resume, + &find_gid, &gid_iter); +resume: + + TST(&gid_iter->list == NULL, ret = NSS_STATUS_NOTFOUND, "Gid not found.", out_dealloc); CHK(fill_group(result, buf, buflen, gid_iter) == 1, diff --git a/rainbow/nss/slist.c b/rainbow/nss/slist.c new file mode 100644 index 0000000..160c17e --- /dev/null +++ b/rainbow/nss/slist.c @@ -0,0 +1,32 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdbool.h> + +#include "slist.h" + +void slist_init(struct slist* self) { + self->next = self; +} + +bool slist_null(struct slist* self) { + return self == self->next; +} + +bool slist_non_null(struct slist* self) { + return self != self->next; +} + +void slist_extend(struct slist* self, struct slist* rhs) { + rhs->next = self->next; + self->next = rhs; +} + +size_t slist_length(struct slist* self) { + /* XXX: Arithmetic overflow! */ + size_t result = 0; + while (slist_non_null(self)) { + result++; + self = self->next; + } + return result; +} diff --git a/rainbow/nss/slist.h b/rainbow/nss/slist.h new file mode 100644 index 0000000..aaccd41 --- /dev/null +++ b/rainbow/nss/slist.h @@ -0,0 +1,50 @@ + +struct slist { struct slist *next; }; + +void slist_init(struct slist* self); +bool slist_null(struct slist* self); +bool slist_non_null(struct slist* self); +size_t slist_length(struct slist* self); +void slist_extend(struct slist* self, struct slist* rhs); + +/* Definition from kernel/include/list.h */ +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) + +/* Definition from kernel/include/list.h */ +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + +/* FUN should return false to break iteration. */ +/* NB: Comma-swallowing paste of gnu-style named variadic macro argument. */ +#define slist_search(TYPE, MEMBER, PTR, FOUND_LABEL, NOTFOUND_LABEL, FUN, COOKIE...) ({ \ + struct slist *__slist_iter = ((PTR)->MEMBER).next; \ + struct slist *__slist_next; \ + while(__slist_iter != &((PTR)->MEMBER)) { \ + __slist_next = __slist_iter->next; \ + TYPE* __value_ptr = container_of(__slist_iter, TYPE, MEMBER); \ + if(!(*(FUN))(__value_ptr, ##COOKIE)) goto FOUND_LABEL; \ + __slist_iter = __slist_next; \ + } \ + goto NOTFOUND_LABEL; }) + +#define slist_while(TYPE, MEMBER, PTR, ERR_LABEL, FUN, COOKIE...) ({ \ + struct slist *__slist_iter = ((PTR)->MEMBER).next; \ + struct slist *__slist_next; \ + while(__slist_iter != &((PTR)->MEMBER)) { \ + __slist_next = __slist_iter->next; \ + TYPE* __value_ptr = container_of(__slist_iter, TYPE, MEMBER); \ + if((*(FUN))(__value_ptr, ##COOKIE)) goto ERR_LABEL; \ + __slist_iter = __slist_next; \ + } \ + }) + +#define slist_for(TYPE, MEMBER, PTR, FUN, COOKIE...) ({ \ + struct slist *__slist_iter = ((PTR)->MEMBER).next; \ + struct slist *__slist_next; \ + while(__slist_iter != &((PTR)->MEMBER)) { \ + __slist_next = __slist_iter->next; \ + TYPE* __value_ptr = container_of(__slist_iter, TYPE, MEMBER); \ + (*(FUN))(__value_ptr, ##COOKIE); \ + __slist_iter = __slist_next; \ + } }) diff --git a/rainbow/nss/test_slist.c b/rainbow/nss/test_slist.c new file mode 100644 index 0000000..66be29d --- /dev/null +++ b/rainbow/nss/test_slist.c @@ -0,0 +1,45 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdbool.h> + +#include "slist.h" + +struct node { + int id; + struct slist list; +}; + +void node_init(struct node* self) { + self->id = 0; + slist_init(&self->list); +} + +void node_print(struct node* self) { + printf("node %d\n", self->id); +} + +int find_two(struct node* self) { + if (self->id == 2) return 0; else return 1; +} + +int main(int argc, char** argv) { + struct node h, a, b, c; + node_init(&h); a.id = 0; + node_init(&a); a.id = 1; + node_init(&b); b.id = 2; + node_init(&c); c.id = 3; + slist_extend(&h.list, &a.list); + slist_extend(&a.list, &b.list); + slist_extend(&b.list, &c.list); + + slist_for(struct node, list, &h, &node_print); + slist_search(struct node, list, &h, found, not_found, &find_two); + +found: + printf("found two\n"); + return 0; + +not_found: + printf("two not found\n"); + return 1; +} |