Reported 23 Jan 2001, by Neal H Walfield <neal@cs.uml.edu> ---------------------------------------------------------- This adds support for in memory directories such as that used in partitionfs. This would be useful in any file system which has relatively static entries (i.e. the file system has control over the creation and the delection of the nodes -- not a /proc or NFS fs). diff -ruN hurd-20000115/libmemdir/ChangeLog hurd-build/libmemdir/ChangeLog --- hurd-20000115/libmemdir/ChangeLog Wed Dec 31 19:00:00 1969 +++ hurd-build/libmemdir/ChangeLog Tue Jan 23 00:01:21 2001 @@ -0,0 +1,4 @@ +2001-01-23 Neal H Walfield <neal@cs.uml.edu> + + * memdir.h, memdir.c: New files. + diff -ruN hurd-20000115/libmemdir/Makefile hurd-build/libmemdir/Makefile --- hurd-20000115/libmemdir/Makefile Wed Dec 31 19:00:00 1969 +++ hurd-build/libmemdir/Makefile Sat Jan 20 15:22:23 2001 @@ -0,0 +1,33 @@ +# +# Copyright (C) 2001 Free Software Foundation +# +# This file is part of the GNU Hurd. +# +# The GNU Hurd is free software; you can redistribute it and/or +# modify it under the terms of the GNU General Public License as +# published by the Free Software Foundation; either version 2, or (at +# your option) any later version. +# +# The GNU Hurd is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + +dir := libmemdir +makemode := library + +libname = libmemdir +SRCS = memdir.c + +LCLHDRS = memdir.h +installhdrs= memdir.h + +HURDLIBS=ihash + +OBJS=$(SRCS:.c=.o) + +include ../Makeconf diff -ruN hurd-20000115/libmemdir/memdir.c hurd-build/libmemdir/memdir.c --- hurd-20000115/libmemdir/memdir.c Wed Dec 31 19:00:00 1969 +++ hurd-build/libmemdir/memdir.c Mon Jan 22 23:58:16 2001 @@ -0,0 +1,625 @@ +/* + Copyright (C) 2001 Free Software Foundation + + Written by Neal H Walfield <neal@cs.uml.edu> + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include <stdlib.h> +#include <string.h> +#include <dirent.h> +#include <error.h> +#include <unistd.h> +#include <sys/mman.h> + +#include <hurd/ihash.h> + +#include "memdir.h" + +static inline void +move_last_entry_to (struct memdir *dir, int pos) +{ + dir->entries[pos] = dir->entries[-- dir->entries_count]; + dir->entries[pos]->position = pos; + dir->invalid = 1; +} + +static inline error_t +make_entry (struct memdir *dir, int *pos) +{ + if (dir->entries_count == dir->entries_allocated) + { + void *temp; + + if (dir->entries_allocated == 0) + { + dir->entries = NULL; + dir->entries_allocated = 1; + } + + temp = realloc (dir->entries, sizeof (struct memdirnode *) + * dir->entries_allocated * 2); + if (! temp) + return ENOMEM; + + dir->entries = temp; + dir->entries_allocated *= 2; + } + + dir->invalid = 1; + *pos = dir->entries_count ++; + return 0; +} + +struct list +{ + /* ihash's location pointer. */ + void **locp; + struct list_element *head; +}; + +struct list_element +{ + struct memdirnode *e; + struct list_element *next; + struct list_element **prevp; +}; + +static inline int +hash_name (char *name) +{ + char *c; + int hash; + int coef; +#define a (3) + + return 0; + + /* From AOC */ + c = name; + hash = *c; + if (*c) + { + coef = a; + for (c ++; *c; c ++) + { + hash += coef * *c; + coef *= a; + } + } + + return hash; +} + +static inline struct memdirnode * +hash_find (struct memdir *dir, char *name, int hash) +{ + struct list *l; + struct list_element *le; + int name_len = strlen (name); + + l = ihash_find (dir->names, hash); + if (! l) + return NULL; + + for (le = l->head; le; le = le->next) + if (name_len == le->e->dirent.d_namlen + && memcmp (name, le->e->dirent.d_name, name_len) == 0) + return le->e; + + return NULL; +} + +static inline error_t +hash_add (struct memdir *dir, struct memdirnode *e, int hash) +{ + error_t err; + struct list *l; + + l = ihash_find (dir->names, hash); + if (! l) + { + l = malloc (sizeof (struct list)); + if (! l) + return ENOMEM; + + l->head = malloc (sizeof (struct list_element)); + if (! l->head) + { + free (l); + return ENOMEM; + } + + l->head->e = e; + l->head->next = NULL; + l->head->prevp = &l->head; + + err = ihash_add (dir->names, hash, l, &l->locp); + return err; + } + else + { + struct list_element *le = malloc (sizeof (struct list_element)); + if (! le) + return ENOMEM; + + le->e = e; + le->next = l->head; + if (le->next) + le->next->prevp = &le->next; + le->prevp = &l->head; + l->head = le; + + return 0; + } +} + +/* Remove element named NAME from the hash. If successful, it will + be returned in E. On failure, *E is cleared.*/ +static inline error_t +hash_remove (struct memdir *dir, struct memdirnode **e, char *name, int hash) +{ + struct list *l; + struct list_element *le; + int name_len; + + l = ihash_find (dir->names, hash); + if (! l) + { + *e = NULL; + return ENOENT; + } + + name_len = strlen (name); + + for (le = l->head; le; le = le->next) + if (name_len == le->e->dirent.d_namlen + && memcmp (name, le->e->dirent.d_name, name_len) == 0) + goto found; + + *e = NULL; + return ENOENT; + + found: + *e = le->e; + + *le->prevp = le->next; + if (le->next) + le->next->prevp = le->prevp; + free (le); + + if (! l->head) + { + ihash_locp_remove (dir->names, l->locp); + free (l); + } + + return 0; +} + +/* Create a new, empty, directory structure. If defined, REMOVE is + called on a node when it is removed from the memdir structure. If + defined, FIND is called in lookup when a node cannot be found. */ +error_t +memdir_create (struct memdir **dir, memdir_entry_remove *remove, + memdir_entry_find *find) +{ + /* Use calloc, we want all members NULL at the start. */ + *dir = calloc (1, sizeof (struct memdir)); + if (! *dir) + return ENOMEM; + + return memdir_init (*dir, remove, find); +} + +/* The same as memdir_create, however, DIR is already allocated. */ +error_t +memdir_init (struct memdir *dir, memdir_entry_remove *remove, + memdir_entry_find *find) +{ + memset (dir, 0, sizeof (struct memdir)); + + dir->remove = remove; + dir->find = find; + + return ihash_create (&dir->names); +} + +/* Free DIR. If there are any entries, EBUSY is returned unless + FORCE is true, then all entries are cleaned and the directory + is freed. */ +error_t +memdir_free (struct memdir *dir, int force) +{ + int i; + + if (dir->entries_count && ! force) + return EBUSY; + + if (dir->listing) + free (dir->listing); + + for (i = 0; i < dir->entries_count; i ++) + { + struct memdirnode *e = dir->entries[i]; + dir->remove (dir, e); + free (e->dirent.d_name); + free (e); + } + + free (dir->entries); + ihash_free (dir->names); + free (dir); + + return 0; +} + +/* Search DIR for node NAME. If found, returned in *E, otherwise *E + is cleared. */ +error_t +memdir_lookup (struct memdir *dir, char *name, struct memdirnode **e) +{ + error_t err; + int hash = hash_name (name); + + start: + *e = hash_find (dir, name, hash); + if (! *e) + { + if (dir->find) + { + err = dir->find (dir, name); + if (! err) + goto start; + } + return ENOENT; + } + + return 0; +} + +/* Add NAME to DIR. If NAME is already present in DIR and REPLACE is + false then EEXIST is returned and if ENTRY is valid, *ENTRY is set + to the current node. If NAME is already present in DIR and REPLACE is + true, the old element is removed (DIR->REMOVE is called) and the new + node generted from NAME takes its place. TYPE is the DT_* name for + the type of node. FILENO is the serial number of the file (almost + always the inode; Cf. info page on struct dirent). If successful + and ENTRY is valid, ENTRY is filled with the new directory entry. */ +error_t +memdir_add (struct memdir *dir, struct memdirnode **entry, char *name, + int type, ino_t fileno, int replace) +{ + error_t err; + int namelen; + int reclen; + int hash; + struct memdirnode *e; + + hash = hash_name (name); + + e = hash_find (dir, name, hash); + if (e && ! replace) + { + if (entry) + *entry = e; + return EEXIST; + } + + if (e) + /* Doing a replace. */ + { + if (dir->remove) + dir->remove (dir, e); + + /* Same name. This is all that we need to change the internal + information. */ + e->dirent.d_type = type; + e->dirent.d_fileno = fileno; + + dir->invalid = 1; + + if (entry) + *entry = e; + + return 0; + } + else + /* Completely new. */ + { + struct dirent dirent; + int pos; + + namelen = strlen (name); + reclen = (sizeof (struct memdirnode) + namelen + 1 + - sizeof (dirent.d_name) + 7) & ~7; /* 8 byte boundary. */ + + e = malloc (reclen); + if (! e) + return ENOMEM; + + err = make_entry (dir, &pos); + if (err) + { + free (e); + if (entry) + *entry = NULL; + return err; + } + + e->position = pos; + dir->entries[pos] = e; + + e->next = dir->entries_list; + if (e->next) + e->next->prevp = &e->next; + e->prevp = &dir->entries_list; + dir->entries_list = e; + + e->node = NULL; + e->dirent.d_type = type; + e->dirent.d_fileno = fileno; + e->dirent.d_namlen = namelen; + e->dirent.d_reclen = reclen; + memcpy (e->dirent.d_name, name, namelen + 1); + + if (entry) + *entry = e; + + return hash_add (dir, e, hash); + } +} + +/* Remove NAME from DIR. If NAME refers to a directory and + FORCE_DIR is false then EISDIR is returned. If NAME refers + to a directory and FORCE_DIR is true then it is removed + is if it were a regular file. DIR->REMOVE is called on the + removed node. */ +error_t +memdir_remove (struct memdir *dir, char *name, int force_dir) +{ + error_t err; + struct memdirnode *e; + int hash = hash_name (name); + + err = hash_remove (dir, &e, name, hash); + if (err) + return err; + + if (dir->remove) + dir->remove (dir, e); + + move_last_entry_to (dir, e->position); + + *e->prevp = e->next; + if (e->next) + e->next->prevp = e->prevp; + + free (e); + + return 0; +} + +/* Rename node FROMNAME to TONAME. If FROMNAME does not exist, + ENOENT is returned. If TONAME exists, EEXIST is returned. */ +error_t +memdir_rename (struct memdir *dir, char *fromname, char *toname) +{ + error_t err; + struct memdirnode *e; + int fromhash, tohash; + + tohash = hash_name (toname); + e = hash_find (dir, toname, tohash); + if (e) + return EEXIST; + + fromhash = hash_name (fromname); + err = hash_remove (dir, &e, fromname, fromhash); + if (err) + return err; + + { + void *temp; + struct dirent dirent; + int namelen; + int reclen; + + namelen = strlen (toname); + reclen = (sizeof (struct memdirnode) + namelen + 1 + - sizeof (dirent.d_name) + 7) & ~7; /* 8 byte boundary. */ + + temp = realloc (e, reclen); + if (! temp) + return ENOMEM; + + if (e != temp) + dir->entries[e->position] = temp; + + e = temp; + + e->dirent.d_namlen = namelen; + e->dirent.d_reclen = reclen; + memcpy (e->dirent.d_name, toname, namelen + 1); + } + + err = hash_add (dir, e, tohash); + if (err) + free (e); + + return err; +} + +/* Iterate over each element in DIR calling FUNC on it. If FUNC ever + returns non-zero, the iteration stops and that value is returned. + Any operation may be performed on the node (e.g. memdir_remove, + memdir_rename), however, only that node may be operated on. */ +error_t +memdir_iterate (struct memdir *dir, + error_t (*func) (struct memdir *dir, struct memdirnode *e, + void *cookie), + void *cookie) +{ + error_t err; + struct memdirnode *node = dir->entries_list; + + while (node) + { + struct memdirnode *next = node->next; + + err = func (dir, node, cookie); + if (err) + return err; + + node = next; + } + + return 0; +} + +/* Return directory contents in a buffer suitable for returning + from a get_dirents RPC (Cf. fs.defs). */ +error_t +memdir_get_dirents (struct memdir *dir, int entry, int nentries, char **data, + size_t *datacnt, vm_size_t bufsize, int *amt) +{ + /* Rebuild the listing. */ + inline error_t + rebuild_listing (void) + { + struct memdirnode *node = dir->entries_list; + + void *buffer = dir->listing; + int allocated = dir->listing_allocated; + int consumed = 0; + int *offsets; + + if (dir->listing_offsets) + free (dir->listing_offsets); + dir->listing_offsets = offsets = malloc (sizeof (int) + * dir->entries_count); + if (! offsets) + return ENOMEM; + + if (allocated == 0) + { + buffer = malloc (allocated = vm_page_size); + if (! buffer) + { + free (offsets); + offsets = NULL; + return ENOMEM; + } + } + + while (node) + { + if (consumed + node->dirent.d_reclen > allocated) + { + void *temp = realloc (buffer, allocated * 2); + if (! temp) + { + free (offsets); + offsets = NULL; + free (buffer); + dir->listing_allocated = 0; + return ENOMEM; + } + + buffer = temp; + allocated *= 2; + } + + + *offsets = consumed; + offsets ++; + + memcpy (buffer + consumed, &node->dirent, node->dirent.d_reclen); + consumed += node->dirent.d_reclen; + + node = node->next; + } + + { + /* Always freeing memory. */ + size_t s = round_page (consumed); + + void *temp = realloc (buffer, s); + if (! temp) + /* WTF?!?! */ + { + free (dir->listing_offsets); + offsets = NULL; + free (buffer); + dir->listing_allocated = 0; + return ENOMEM; + } + + dir->listing = temp; + dir->listing_allocated = s; + dir->listing_size = consumed; + } + + dir->invalid = 0; /* Ahh. */ + return 0; + } + + error_t err; + + size_t need; + size_t allocsize; + + struct dirent *first; + struct dirent *last; + + /* If they are asking something we do not have, stop now. */ + if (entry >= dir->entries_count) + { + *amt = 0; + *datacnt = 0; + return 0; + } + + if (dir->invalid) + { + err = rebuild_listing (); + if (err) + return err; + } + + if (nentries == -1) + nentries = dir->entries_count - entry; + + if (entry == 0) + first = dir->listing; + else + first = dir->listing + dir->listing_offsets[entry]; + + last = dir->listing + dir->listing_offsets[entry + nentries - 1]; + need = (void *) last + last->d_reclen - (void *) first; + + if (! bufsize || bufsize > need) + allocsize = round_page (need); + else + allocsize = round_page (bufsize); + if (allocsize > *datacnt) + *data = mmap (0, allocsize, PROT_READ|PROT_WRITE, MAP_ANON, 0, 0); + + *datacnt = allocsize > need ? need : allocsize; + memcpy (*data, dir->listing, *datacnt); + + *amt = nentries; + return 0; +} diff -ruN hurd-20000115/libmemdir/memdir.h hurd-build/libmemdir/memdir.h --- hurd-20000115/libmemdir/memdir.h Wed Dec 31 19:00:00 1969 +++ hurd-build/libmemdir/memdir.h Mon Jan 22 23:56:18 2001 @@ -0,0 +1,156 @@ +/* + Copyright (C) 2001 Free Software Foundation + + Written by Neal H Walfield <neal@cs.uml.edu> + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* This library manages directories for users who want to + write filesystem servers. */ + +#ifndef MEMDIR_H +#define MEMDIR_H + +#include <dirent.h> +#include <hurd.h> +#include <hurd/ihash.h> + +struct node; + +struct memdirnode +{ + /* User data. */ + struct node *node; + + /* Entry in the dir->entries array; Do not change. */ + int position; + /* Linked list of all dirnodes in this directory; Private. */ + struct memdirnode *next; + struct memdirnode **prevp; + + /* Recall: dirent is dynamic; Do not touch d_name, d_namlen or d_reclen + directly. Use the provided functions. */ + struct dirent dirent; +}; + +struct memdir; /* Forward. */ + +typedef void memdir_entry_remove (struct memdir *dir, struct memdirnode *); +typedef error_t memdir_entry_find (struct memdir *dir, char *name); + +struct memdir +{ + /* Called when a node is about to be removed. */ + memdir_entry_remove *remove; + + /* Called when a lookup on a directory fails. If this routine returns + success, the lookup will then be repeated. If it returns an error, + then the lookup will fail with the reported error. */ + memdir_entry_find *find; + + /* Suitable for returning from get_dirents iff valid is true. */ + void *listing; + int invalid; + /* Size in bytes. */ + int listing_size; + /* Actual amount of storage available. */ + int listing_allocated; + /* Element offset into listing; one for everyone. */ + int *listing_offsets; + + /* An array of pointers to dirents created on ENTER*. */ + struct memdirnode **entries; + /* Record count. */ + int entries_count; + /* Records allocated. */ + int entries_allocated; + + /* The linked list of nodes. */ + struct memdirnode *entries_list; + + /* Hash by directory names. */ + ihash_t names; + + /* User hook. */ + void *hook; +}; + + +/* Create a new, empty, directory structure. If defined, REMOVE is + called on a node when it is removed from the memdir structure. If + defined, FIND is called in lookup when a node cannot be found. */ +error_t +memdir_create (struct memdir **dir, memdir_entry_remove *remove, + memdir_entry_find *find); + +/* The same as memdir_create, however, DIR is already allocated. */ +error_t +memdir_init (struct memdir *dir, memdir_entry_remove *remove, + memdir_entry_find *find); + +/* Free a DIR. If there are any entries, EBUSY is returned unless + FORCE is true, then all entries are cleaned and the directory + is freed. */ +error_t +memdir_free (struct memdir *dir, int force); + +/* Search DIR for node NAME. If found, return in *E, otherwise *E + is cleared. */ +error_t +memdir_lookup (struct memdir *dir, char *name, struct memdirnode **e); + +/* Add NAME to DIR. If NAME is already present in DIR and REPLACE is + false then EEXIST is returned and if ENTRY is valid, *ENTRY is set + to the current node. If NAME is already present in DIR and REPLACE is + true, the old element is removed (DIR->REMOVE is called) and the new + node generted from NAME takes its place. TYPE is the DT_* name for + the type of node. FILENO is the serial number of the file (almost + always the inode; Cf. info page on struct dirent). If successful + and ENTRY is valid, ENTRY is filled with the new directory entry. */ +error_t +memdir_add (struct memdir *dir, struct memdirnode **e, char *name, + int type, ino_t fileno, int replace); + +/* Remove NAME from DIR. If NAME refers to a directory and + FORCE_DIR is false then EISDIR is returned. If NAME refers + to a directory and FORCE_DIR is true then it is removed + is if it were a regular file. DIR->REMOVE is called on the + removed node. */ +error_t +memdir_remove (struct memdir *dir, char *name, int force_dir); + +/* Rename node FROMNAME to TONAME. If FROMNAME does not exist, + ENOENT is returned. If TONAME exists, EEXIST is returned. */ +error_t +memdir_rename (struct memdir *dir, char *fromname, char *toname); + +/* Iterate over each element in DIR calling FUNC on it. If FUNC ever + returns non-zero, the iteration stops and that value is returned. + Any operation may be performed on the node (e.g. memdir_remove, + memdir_rename), however, only that node may be operated on. */ +error_t +memdir_iterate (struct memdir *dir, + error_t (*func) (struct memdir *dir, struct memdirnode *e, + void *cookie), + void *cookie); + + +/* Return directory contents in a buffer suitable for returning + from a get_dirents RPC (Cf. fs.defs). */ +error_t +memdir_get_dirents (struct memdir *dir, int entry, int nentries, char **data, + size_t *datacnt, vm_size_t bufsize, int *amt); + +#endif /* MEMDIR_H */ --- hurd-20000115/Makefile Thu Nov 18 01:31:24 1999 +++ hurd-build/Makefile Sat Jan 20 15:22:44 2001 @@ -30,7 +30,8 @@ # Hurd libraries lib-subdirs = libshouldbeinlibc libihash libiohelp libports libthreads \ libpager libfshelp libdiskfs libtrivfs libps \ - libnetfs libpipe libstore libhurdbugaddr libftpconn + libnetfs libpipe libstore libhurdbugaddr libftpconn \ + libmemdir # Hurd programs prog-subdirs = auth proc exec init term \ --- hurd-20000115/ChangeLog Thu May 25 15:23:28 2000 +++ hurd-build/ChangeLog Tue Jan 23 00:04:00 2001 @@ -1,3 +1,7 @@ +2001-01-23 Neal H Walfield <neal@cs.uml.edu> + + * Makefile: Add support for building libmemdir + 2000-05-20 Mark Kettenis <kettenis@gnu.org> * configure.in: Add check for libio. Only enable versioning if we