Add a novel singly-linked list implementation.

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;
+}