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 + + * 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 + + 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 +#include +#include +#include +#include +#include + +#include + +#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 + + 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 +#include +#include + +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 + + * Makefile: Add support for building libmemdir + 2000-05-20 Mark Kettenis * configure.in: Add check for libio. Only enable versioning if we