| Age | Commit message (Collapse) | Author |
|---|
|
* libdiskfs/name-cache.c: Move the Murmur3 algorithm...
* libihash/murmur3.c: ... here, and properly attribute the code.
* libihash/ihash.h (hurd_ihash_hash32): New prototype.
* libihash/Makefile (SRCS): Add new file.
|
|
* libdiskfs/name-cache.c (diskfs_check_lookup_cache): Drop stray negation.
|
|
Previously, name cache lookup operation completed in O(n) time. This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size.
Implement the name cache using a hash table.
We use buckets of a fixed size. We approximate the least-frequently
used cache algorithm by counting the number of lookups using
saturating arithmetic in the two lowest bits of the pointer to the
name. Using this strategy we achieve a constant worst-case lookup and
insertion time.
Since we are not bound by the size of the cache anymore, increase its
size from 200 to 1024.
* libdiskfs/name-cache.c: Implement the name cache using a hash table.
(diskfs_enter_lookup_cache): Change accordingly.
(diskfs_purge_lookup_cache): Likewise.
(diskfs_check_lookup_cache): Likewise. Also, hard code a
cache miss for the parent of the root directory and merge unlocking
and releasing of node references.
|
|
The current name cache lookup operation completes in O(n) time. This
means that making the cache too large would decrease the performance.
Therefore it was required to tune the size, hence the need for
statistics.
We will use a data structure with worst case constant lookup times in
the future, removing the need to fine tune the cache size.
* libdiskfs/name-cache.c: Remove the statistics code from the name
cache.
|
|
* libdiskfs/name-cache.c (diskfs_check_lookup_cache): Release node
reference in a special case of lookup failure.
|
|
* libdiskfs/name-cache.c (struct lookup_cache): Fix type of
dir_cache_id, node_cache_id.
|
|
Makefiles, headers, types, macros and function calls are renamed where
appropriate.
Most of this work was done by Barry deFreese and Thomas DiModica.
* auth/Makefile: Switch from cthreads to pthreads.
* auth/auth.c: Likewise.
* boot/Makefile: Likewise.
* boot/boot.c: Likewise.
* boot/ux.c: Likewise.
* console-client/Makefile: Likewise.
* console-client/console.c: Likewise.
* console-client/driver.c: Likewise.
* console-client/driver.h: Likewise.
* console-client/generic-speaker.c: Likewise.
* console-client/kbd-repeat.c: Likewise.
* console-client/ncursesw.c: Likewise.
* console-client/pc-kbd.c: Likewise.
* console-client/pc-mouse.c: Likewise.
* console-client/timer.c: Likewise.
* console-client/trans.c: Likewise.
* console-client/vga.c: Likewise.
* console/Makefile: Likewise.
* console/console.c: Likewise.
* console/display.c: Likewise.
* console/input.c: Likewise.
* console/pager.c: Likewise.
* defpager/backing.c: Likewise.
* exec/Makefile: Likewise.
* exec/exec.c: Likewise.
* exec/hashexec.c: Likewise.
* exec/priv.h: Likewise.
* ext2fs/Makefile: Likewise.
* ext2fs/balloc.c: Likewise.
* ext2fs/dir.c: Likewise.
* ext2fs/ext2fs.c: Likewise.
* ext2fs/ext2fs.h: Likewise.
* ext2fs/ialloc.c: Likewise.
* ext2fs/inode.c: Likewise.
* ext2fs/msg.c: Likewise.
* ext2fs/pager.c: Likewise.
* ext2fs/pokel.c: Likewise.
* ext2fs/storeinfo.c: Likewise.
* ext2fs/truncate.c: Likewise.
* fatfs/Makefile: Likewise.
* fatfs/dir.c: Likewise.
* fatfs/fat.c: Likewise.
* fatfs/fatfs.h: Likewise.
* fatfs/inode.c: Likewise.
* fatfs/main.c: Likewise.
* fatfs/pager.c: Likewise.
* fatfs/virt-inode.c: Likewise.
* ftpfs/Makefile: Likewise.
* ftpfs/ccache.c: Likewise.
* ftpfs/ccache.h: Likewise.
* ftpfs/conn.c: Likewise.
* ftpfs/dir.c: Likewise.
* ftpfs/fs.c: Likewise.
* ftpfs/ftpfs.c: Likewise.
* ftpfs/ftpfs.h: Likewise.
* ftpfs/ncache.c: Likewise.
* ftpfs/netfs.c: Likewise.
* ftpfs/node.c: Likewise.
* hostmux/Makefile: Likewise.
* hostmux/hostmux.h: Likewise.
* hostmux/mux.c: Likewise.
* hostmux/node.c: Likewise.
* hostmux/stubs.c: Likewise.
* hurd/shared.h: Likewise.
* isofs/Makefile: Likewise.
* isofs/inode.c: Likewise.
* isofs/lookup.c: Likewise.
* isofs/main.c: Likewise.
* isofs/pager.c: Likewise.
* libcons/Makefile: Likewise.
* libcons/cons-switch.c: Likewise.
* libcons/cons.h: Likewise.
* libcons/dir-changed.c: Likewise.
* libcons/file-changed.c: Likewise.
* libcons/init-init.c: Likewise.
* libcons/vcons-close.c: Likewise.
* libcons/vcons-input.c: Likewise.
* libcons/vcons-move-mouse.c: Likewise.
* libcons/vcons-open.c: Likewise.
* libcons/vcons-scrollback.c: Likewise.
* libdiskfs/Makefile: Likewise.
* libdiskfs/boot-start.c: Likewise.
* libdiskfs/dead-name.c: Likewise.
* libdiskfs/dir-chg.c: Likewise.
* libdiskfs/dir-link.c: Likewise.
* libdiskfs/dir-lookup.c: Likewise.
* libdiskfs/dir-mkdir.c: Likewise.
* libdiskfs/dir-mkfile.c: Likewise.
* libdiskfs/dir-readdir.c: Likewise.
* libdiskfs/dir-rename.c: Likewise.
* libdiskfs/dir-renamed.c: Likewise.
* libdiskfs/dir-rmdir.c: Likewise.
* libdiskfs/dir-unlink.c: Likewise.
* libdiskfs/disk-pager.c: Likewise.
* libdiskfs/diskfs-pager.h: Likewise.
* libdiskfs/diskfs.h: Likewise.
* libdiskfs/file-access.c: Likewise.
* libdiskfs/file-chg.c: Likewise.
* libdiskfs/file-exec.c: Likewise.
* libdiskfs/file-get-fs-opts.c: Likewise.
* libdiskfs/file-get-trans.c: Likewise.
* libdiskfs/file-get-transcntl.c: Likewise.
* libdiskfs/file-getcontrol.c: Likewise.
* libdiskfs/file-getfh.c: Likewise.
* libdiskfs/file-lock-stat.c: Likewise.
* libdiskfs/file-lock.c: Likewise.
* libdiskfs/file-reparent.c: Likewise.
* libdiskfs/file-set-trans.c: Likewise.
* libdiskfs/file-sync.c: Likewise.
* libdiskfs/file-syncfs.c: Likewise.
* libdiskfs/fsys-getroot.c: Likewise.
* libdiskfs/fsys-options.c: Likewise.
* libdiskfs/fsys-syncfs.c: Likewise.
* libdiskfs/ifsock.c: Likewise.
* libdiskfs/init-first.c: Likewise.
* libdiskfs/init-init.c: Likewise.
* libdiskfs/init-startup.c: Likewise.
* libdiskfs/io-duplicate.c: Likewise.
* libdiskfs/io-get-conch.c: Likewise.
* libdiskfs/io-identity.c: Likewise.
* libdiskfs/io-map-cntl.c: Likewise.
* libdiskfs/io-map.c: Likewise.
* libdiskfs/io-modes-get.c: Likewise.
* libdiskfs/io-modes-off.c: Likewise.
* libdiskfs/io-modes-on.c: Likewise.
* libdiskfs/io-modes-set.c: Likewise.
* libdiskfs/io-owner-get.c: Likewise.
* libdiskfs/io-owner-mod.c: Likewise.
* libdiskfs/io-prenotify.c: Likewise.
* libdiskfs/io-read.c: Likewise.
* libdiskfs/io-readable.c: Likewise.
* libdiskfs/io-reauthenticate.c: Likewise.
* libdiskfs/io-rel-conch.c: Likewise.
* libdiskfs/io-restrict-auth.c: Likewise.
* libdiskfs/io-revoke.c: Likewise.
* libdiskfs/io-seek.c: Likewise.
* libdiskfs/io-sigio.c: Likewise.
* libdiskfs/io-stat.c: Likewise.
* libdiskfs/io-write.c: Likewise.
* libdiskfs/lookup.c: Likewise.
* libdiskfs/name-cache.c: Likewise.
* libdiskfs/node-drop.c: Likewise.
* libdiskfs/node-make.c: Likewise.
* libdiskfs/node-nput.c: Likewise.
* libdiskfs/node-nputl.c: Likewise.
* libdiskfs/node-nref.c: Likewise.
* libdiskfs/node-nrefl.c: Likewise.
* libdiskfs/node-nrele.c: Likewise.
* libdiskfs/node-nrelel.c: Likewise.
* libdiskfs/peropen-rele.c: Likewise.
* libdiskfs/priv.h: Likewise.
* libdiskfs/shutdown.c: Likewise.
* libdiskfs/sync-interval.c: Likewise.
* libfshelp/Makefile: Likewise.
* libfshelp/fetch-root.c: Likewise.
* libfshelp/fshelp.h: Likewise.
* libfshelp/get-identity.c: Likewise.
* libfshelp/lock-acquire.c: Likewise.
* libfshelp/lock-init.c: Likewise.
* libfshelp/locks.h: Likewise.
* libfshelp/set-active.c: Likewise.
* libfshelp/trans.h: Likewise.
* libfshelp/transbox-init.c: Likewise.
* libiohelp/Makefile: Likewise.
* libiohelp/get_conch.c: Likewise.
* libiohelp/handle_io_release_conch.c: Likewise.
* libiohelp/initialize_conch.c: Likewise.
* libiohelp/iohelp.h: Likewise.
* libiohelp/verify_user_conch.c: Likewise.
* libnetfs/Makefile: Likewise.
* libnetfs/dir-lookup.c: Likewise.
* libnetfs/dir-mkdir.c: Likewise.
* libnetfs/dir-mkfile.c: Likewise.
* libnetfs/dir-readdir.c: Likewise.
* libnetfs/dir-rmdir.c: Likewise.
* libnetfs/dir-unlink.c: Likewise.
* libnetfs/drop-node.c: Likewise.
* libnetfs/file-chauthor.c: Likewise.
* libnetfs/file-check-access.c: Likewise.
* libnetfs/file-chflags.c: Likewise.
* libnetfs/file-chmod.c: Likewise.
* libnetfs/file-chown.c: Likewise.
* libnetfs/file-exec.c: Likewise.
* libnetfs/file-get-storage-info.c: Likewise.
* libnetfs/file-get-translator.c: Likewise.
* libnetfs/file-lock-stat.c: Likewise.
* libnetfs/file-lock.c: Likewise.
* libnetfs/file-reparent.c: Likewise.
* libnetfs/file-set-size.c: Likewise.
* libnetfs/file-set-translator.c: Likewise.
* libnetfs/file-statfs.c: Likewise.
* libnetfs/file-sync.c: Likewise.
* libnetfs/file-syncfs.c: Likewise.
* libnetfs/file-utimes.c: Likewise.
* libnetfs/fsys-getroot.c: Likewise.
* libnetfs/fsys-set-options.c: Likewise.
* libnetfs/init-init.c: Likewise.
* libnetfs/io-clear-some-openmodes.c: Likewise.
* libnetfs/io-duplicate.c: Likewise.
* libnetfs/io-get-openmodes.c: Likewise.
* libnetfs/io-get-owner.c: Likewise.
* libnetfs/io-identity.c: Likewise.
* libnetfs/io-mod-owner.c: Likewise.
* libnetfs/io-read.c: Likewise.
* libnetfs/io-readable.c: Likewise.
* libnetfs/io-reauthenticate.c: Likewise.
* libnetfs/io-restrict-auth.c: Likewise.
* libnetfs/io-revoke.c: Likewise.
* libnetfs/io-seek.c: Likewise.
* libnetfs/io-set-all-openmodes.c: Likewise.
* libnetfs/io-set-some-openmodes.c: Likewise.
* libnetfs/io-stat.c: Likewise.
* libnetfs/io-write.c: Likewise.
* libnetfs/make-node.c: Likewise.
* libnetfs/netfs.h: Likewise.
* libnetfs/nput.c: Likewise.
* libnetfs/nref.c: Likewise.
* libnetfs/nrele.c: Likewise.
* libnetfs/release-peropen.c: Likewise.
* libnetfs/shutdown.c: Likewise.
* libpager/Makefile: Likewise.
* libpager/chg-compl.c: Likewise.
* libpager/clean.c: Likewise.
* libpager/data-request.c: Likewise.
* libpager/data-return.c: Likewise.
* libpager/data-unlock.c: Likewise.
* libpager/inhibit-term.c: Likewise.
* libpager/lock-completed.c: Likewise.
* libpager/lock-object.c: Likewise.
* libpager/mark-error.c: Likewise.
* libpager/no-senders.c: Likewise.
* libpager/object-init.c: Likewise.
* libpager/object-terminate.c: Likewise.
* libpager/offer-page.c: Likewise.
* libpager/pager-attr.c: Likewise.
* libpager/pager-create.c: Likewise.
* libpager/pager-shutdown.c: Likewise.
* libpager/priv.h: Likewise.
* libpager/seqnos.c: Likewise.
* libpipe/Makefile: Likewise.
* libpipe/pipe.c: Likewise.
* libpipe/pipe.h: Likewise.
* libports/Makefile: Likewise.
* libports/begin-rpc.c: Likewise.
* libports/bucket-iterate.c: Likewise.
* libports/claim-right.c: Likewise.
* libports/class-iterate.c: Likewise.
* libports/complete-deallocate.c: Likewise.
* libports/count-bucket.c: Likewise.
* libports/count-class.c: Likewise.
* libports/create-bucket.c: Likewise.
* libports/create-internal.c: Likewise.
* libports/destroy-right.c: Likewise.
* libports/enable-bucket.c: Likewise.
* libports/enable-class.c: Likewise.
* libports/end-rpc.c: Likewise.
* libports/get-right.c: Likewise.
* libports/import-port.c: Likewise.
* libports/inhibit-all-rpcs.c: Likewise.
* libports/inhibit-bucket-rpcs.c: Likewise.
* libports/inhibit-class-rpcs.c: Likewise.
* libports/inhibit-port-rpcs.c: Likewise.
* libports/init.c: Likewise.
* libports/interrupt-notified-rpcs.c: Likewise.
* libports/interrupt-on-notify.c: Likewise.
* libports/interrupt-operation.c: Likewise.
* libports/interrupt-rpcs.c: Likewise.
* libports/interrupted.c: Likewise.
* libports/lookup-port.c: Likewise.
* libports/manage-multithread.c: Likewise.
* libports/no-senders.c: Likewise.
* libports/port-deref-weak.c: Likewise.
* libports/port-deref.c: Likewise.
* libports/port-ref-weak.c: Likewise.
* libports/port-ref.c: Likewise.
* libports/ports.h: Likewise.
* libports/reallocate-from-external.c: Likewise.
* libports/reallocate-port.c: Likewise.
* libports/resume-all-rpcs.c: Likewise.
* libports/resume-bucket-rpcs.c: Likewise.
* libports/resume-class-rpcs.c: Likewise.
* libports/resume-port-rpcs.c: Likewise.
* libports/stubs.c: Likewise.
* libports/transfer-right.c: Likewise.
* libstore/Makefile: Likewise.
* libstore/gunzip.c: Likewise.
* libstore/part.c: Likewise.
* libstore/unzipstore.c: Likewise.
* libthreads/Makefile: Likewise.
* libtreefs/dir-lookup.c: Likewise.
* libtreefs/fsys-getroot.c: Likewise.
* libtreefs/fsys-hooks.c: Likewise.
* libtreefs/fsys.c: Likewise.
* libtreefs/trans-help.c: Likewise.
* libtreefs/trans-start.c: Likewise.
* libtreefs/treefs.h: Likewise.
* libtrivfs/cntl-create.c: Likewise.
* libtrivfs/dyn-classes.c: Likewise.
* libtrivfs/io-reauthenticate.c: Likewise.
* libtrivfs/io-restrict-auth.c: Likewise.
* libtrivfs/protid-clean.c: Likewise.
* libtrivfs/protid-dup.c: Likewise.
* libtrivfs/trivfs.h: Likewise.
* mach-defpager/Makefile: Likewise.
* mach-defpager/default_pager.c: Likewise.
* mach-defpager/kalloc.c: Likewise.
* mach-defpager/main.c: Likewise.
* nfs/Makefile: Likewise.
* nfs/cache.c: Likewise.
* nfs/main.c: Likewise.
* nfs/mount.c: Likewise.
* nfs/name-cache.c: Likewise.
* nfs/nfs.h: Likewise.
* nfs/ops.c: Likewise.
* nfs/rpc.c: Likewise.
* nfsd/Makefile: Likewise.
* nfsd/cache.c: Likewise.
* nfsd/loop.c: Likewise.
* nfsd/main.c: Likewise.
* nfsd/nfsd.h: Likewise.
* pfinet/Makefile: Likewise.
* pfinet/ethernet.c: Likewise.
* pfinet/glue-include/asm/spinlock.h: Likewise.
* pfinet/glue-include/linux/interrupt.h: Likewise.
* pfinet/glue-include/linux/sched.h: Likewise.
* pfinet/glue-include/linux/timer.h: Likewise.
* pfinet/glue-include/linux/wait.h: Likewise.
* pfinet/iioctl-ops.c: Likewise.
* pfinet/io-ops.c: Likewise.
* pfinet/kmem_cache.c: Likewise.
* pfinet/main.c: Likewise.
* pfinet/options.c: Likewise.
* pfinet/pfinet-ops.c: Likewise.
* pfinet/pfinet.h: Likewise.
* pfinet/sched.c: Likewise.
* pfinet/socket-ops.c: Likewise.
* pfinet/socket.c: Likewise.
* pfinet/timer-emul.c: Likewise.
* pfinet/tunnel.c: Likewise.
* pflocal/Makefile: Likewise.
* pflocal/connq.c: Likewise.
* pflocal/io.c: Likewise.
* pflocal/sock.c: Likewise.
* pflocal/sock.h: Likewise.
* pflocal/socket.c: Likewise.
* pflocal/sserver.c: Likewise.
* proc/Makefile: Likewise.
* proc/info.c: Likewise.
* proc/main.c: Likewise.
* proc/mgt.c: Likewise.
* proc/msg.c: Likewise.
* proc/proc.h: Likewise.
* proc/stubs.c: Likewise.
* proc/wait.c: Likewise.
* storeio/Makefile: Likewise.
* storeio/dev.c: Likewise.
* storeio/dev.h: Likewise.
* storeio/open.c: Likewise.
* storeio/open.h: Likewise.
* storeio/pager.c: Likewise.
* storeio/storeio.c: Likewise.
* term/Makefile: Likewise.
* term/devio.c: Likewise.
* term/hurdio.c: Likewise.
* term/main.c: Likewise.
* term/munge.c: Likewise.
* term/ptyio.c: Likewise.
* term/term.h: Likewise.
* term/users.c: Likewise.
* tmpfs/Makefile: Likewise.
* tmpfs/dir.c: Likewise.
* tmpfs/node.c: Likewise.
* tmpfs/tmpfs.c: Likewise.
* tmpfs/tmpfs.h: Likewise.
* trans/Makefile: Likewise.
* trans/fakeroot.c: Likewise.
* trans/fifo.c: Likewise.
* trans/hello-mt.c: Likewise.
* trans/new-fifo.c: Likewise.
* trans/streamio.c: Likewise.
* ufs/Makefile: Likewise.
* ufs/alloc.c: Likewise.
* ufs/dir.c: Likewise.
* ufs/hyper.c: Likewise.
* ufs/inode.c: Likewise.
* ufs/main.c: Likewise.
* ufs/pager.c: Likewise.
* ufs/pokeloc.c: Likewise.
* ufs/sizes.c: Likewise.
* ufs/ufs.h: Likewise.
* usermux/Makefile: Likewise.
* usermux/mux.c: Likewise.
* usermux/node.c: Likewise.
* usermux/usermux.h: Likewise.
* utils/Makefile: Likewise.
* utils/fakeauth.c: Likewise.
* utils/rpctrace.c: Likewise.
|
|
* diskfs.h (diskfs_lookup_hard, diskfs_lookup,
diskfs_set_translator, diskfs_create_symlink_hook,
diskfs_notice_dirchange, diskfs_direnter, diskfs_direnter_hard,
diskfs_dirrewrite, diskfs_dirremove,
diskfs_create_node, diskfs_enter_lookup_cache,
diskfs_check_lookup_cache, dir_rename_dir, diskfs_set_options):
Add `const' qualifier to `char *' parameters where appropriate.
* opts-set.c (diskfs_set_options): Fix defn with `const'.
* node-create.c (diskfs_create_node): Likewise.
* name-cache.c (diskfs_enter_lookup_cache): Likewise.
(diskfs_check_lookup_cache): Likewise.
* dirremove.c (diskfs_dirremove): Likewise.
* dirrewrite.c (diskfs_dirrewrite): Likewise.
* lookup.c (diskfs_lookup): Likewise.
* direnter.c (diskfs_direnter): Likewise.
* dir-renamed.c (diskfs_rename_dir): Likewise.
* dir-chg.c (diskfs_notice_dirchange): Likewise.
|
|
* name-cache.c (find_cache): Grammar doc fix.
|
|
|
|
(lookup_cache): Change type to struct cacheq.
(mru_cache, lru_cache): Variables removed.
(make_mru, make_lru, init_lookup_cache): Functions removed.
(find_cache, diskfs_purge_lookup_cache, diskfs_check_lookup_cache): Use
cacheq functions.
|
|
|
|
Add NEXT & PREV fields.
Rename LEN back to NAME_LEN.
(lru_cache, mru_cache):
New variables.
(first_cache, last_cache):
Variables removed.
(make_mru, make_lru, find_cache, init_lookup_cache):
New functions.
(diskfs_enter_lookup_cache, diskfs_purge_lookup_cache,
diskfs_check_lookup_cache):
Rewrite to use the linked list.
Deal with negative entries.
Reuse old entries for the given name.
|
|
Correctly handle the case where the lookup returns DIR itself.
(diskfs_enter_lookup_cache, diskfs_purge_lookup_cache,
diskfs_check_lookup_cache):
Renamed from versions without `lookup_'.
(diskfs_check_cache): Declare I.
(struct lookup_cache, diskfs_enter_cache): Change NAMELEN field to LEN.
(_diskfs_purge_cache_deletion): Delete function.
|
|
LOOKUP_CACHE_TAIL back itself too.
(_diskfs_purge_cache_deletion): Likewise.
|
|
|
|
(diskfs_check_cache): Keep statistics on cache performance.
|
|
|
|
|
