| Age | Commit message (Collapse) | Author |
|---|
|
|
|
* configure.ac: Call AC_NO_EXECUTABLES when cross-compiling.
|
|
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.
|
|
When using fat nodes, expressions of the form E->nn can be rewritten
as netfs_node_netnode (E). This is much faster as it only involves a
offset calculation. For reference, I used the following semantic
patch to create the patch:
@@
expression E;
@@
- E->nn
+ netfs_node_netnode (E)
* trans/fakeroot.c: Use netfs_node_netnode instead of np->nn.
|
|
Previously, fakeroot stored netnodes in the hash table. But we are
not interested in a cache for netnodes, we need a node cache. So
fakeroot kept pointers to the associated node object in each netnode
object.
Use fat netfs nodes, which combine node and netnode objects.
* trans/fakeroot.c (struct netnode): Remove np.
(idport_ihash): Fix ihash location pointer offset.
(new_node): Allocate fat nodes, store the node pointer in the hash
table.
(netfs_node_norefs): Adjust accordingly.
(netfs_S_dir_lookup): Likewise.
|
|
libnetfs has two kind of nodes, struct node and struct netnode.
struct node is used to store libnetfs specific data, while struct
netnode contains user supplied data. Previously, both objects were
allocated separatly, and a pointer from the node to the netnode
provided a mapping from the former to the latter.
Provide a function netfs_make_node_alloc that allocates both nodes in
a contiguous region.
This reduces the memory allocation overhead when creating nodes. It
also makes the relation between node and netnode a simple offset
calculation. Provide two functions to compute the netnode address
from the node address and vice-versa.
Most notably, this makes implementing a cache on top of libnetfs
easier. Auxiliary data for the cache can be stored in the
user-defined netnode, and the fat node can be used as the value.
* libnetfs/make-node.c (init_node): Move initialization here.
(netfs_make_node): Use init_node.
(netfs_make_node_alloc): New function to allocate fat nodes.
* libnetfs/netfs.h (netfs_make_node_alloc): New declaration.
(_netfs_sizeof_struct_node): Likewise.
(netfs_node_netnode): Compute netnode address from node address.
(netfs_netnode_node): And vice-versa.
* libnetfs/init-init.c (_netfs_sizeof_struct_node): New variable.
|
|
libdiskfs has two kind of nodes, struct node and struct netnode.
struct node is used to store libdiskfs specific data, while struct
netnode contains user supplied data. Previously, both objects were
allocated separatly, and a pointer from the node to the netnode
provided a mapping from the former to the latter.
Provide a function diskfs_make_node_alloc that allocates both nodes in
a contiguous region.
This reduces the memory allocation overhead when creating nodes. It
also makes the relation between node and netnode a simple offset
calculation. Provide two functions to compute the netnode address
from the node address and vice-versa.
Most notably, this makes implementing a cache on top of libdiskfs
easier. Auxiliary data for the cache can be stored in the
user-defined netnode, and the fat node can be used as the value.
* libdiskfs/node-make.c (init_node): Move initialization here.
(diskfs_make_node): Use init_node.
(diskfs_make_node_alloc): New function to allocate fat nodes.
* libdiskfs/diskfs.h (diskfs_make_node_alloc): New declaration.
(_diskfs_sizeof_struct_node): Likewise.
(diskfs_node_disknode): Compute disknode address from node address.
(diskfs_disknode_node): And vice-versa.
* libdiskfs/init-init.c (_diskfs_sizeof_struct_node): New variable.
|
|
* libtrivfs/trivfs.h (struct trivfs_peropen): Use refcount_t for field
refcnt.
(struct trivfs_control): Remove unused field lock.
* libtrivfs/cntl-create.c (trivfs_create_control): Drop the mutex
initialization.
* libtrivfs/io-reauthenticate.c (trivfs_S_io_reauthenticate): Adjust
accordingly.
* libtrivfs/io-restrict-auth.c (trivfs_S_io_restrict_auth): Likewise.
* libtrivfs/open.c (trivfs_open): Initialize refcnt.
* libtrivfs/protid-clean.c (trivfs_clean_protid): Likewise.
* libtrivfs/protid-dup.c (trivfs_protid_dup): Likewise.
|
|
Recently libihash was changed to use an integer hash function on the
keys in an attempt to reduce the rate of collisions (2d898893), which
has long been assumed to be high.
Richard Braun was kind enough to run some benchmarks. He observed:
"1/ Using an extremely simple microbenchmark [1] that merely inserts
keys, either random integers or sequential ones to match the way port
names are managed, it seems that the previous code, despite its
apparent flaws, did quite well.
[1] http://darnassus.sceen.net/gitweb/rbraun/ihtest.git
Using an integer hashing function actually reduces performance on the
sequential integer test case. It makes sense because, considering a
set of consecutive integers starting from 0, and a hash table that
always has more slots than items, a modulo is a perfect hash
function. Even when taking into account that only names for receive
rights are normally managed with libihash, i.e. that keys aren't
actually sequential, they are almost all equally distributed, leading
to very few collisions.
Therefore, as a third option, I've removed the hashing function,
leaving only a fast modulo (an AND) and this variant provided the best
raw results.
2/ I've also built hurd packages multiple times and got average build
times with each variant (previous, new, new without hash function) and
here are the results I obtained respectively : 52m59s, 52m31s, 52m22s."
Do not use the integer hash function on the keys by default.
* libihash/ihash.c (murmur3_mix32): Remove now unused function.
(find_index): Use the fast division method to derive the index.
(add_one): Likewise. Also, update the comment to reflect the current
hashing method.
|
|
* libdiskfs/name-cache.c (diskfs_check_lookup_cache): Release node
reference in a special case of lookup failure.
|
|
* trans/mtab.c (main): Fix initialization of mtab in one-shot mode.
|
|
This fixes a bug introduced in 86122789.
* ext2fs/pager.c (diskfs_pager_users): We count file_pager_bucket,
which does not include the disk pagers. Fix condition accordingly.
|
|
* libpager/priv.h (struct pager): Drop fields next, pprev.
|
|
I tested this change for some days and have not experienced any
problems with it.
* term/users.c (pi_destroy_hook): Fix memory leak.
|
|
Make empty bodies of control flow statements more explicit. Doing so
will allow us to use stricter compiler settings. This would have
cought 4ece292c.
* console-client/xkb/xkb.c: Make empty bodies more explicit
* libpipe/pipe.c: Likewise.
* mach-defpager/default_pager.c: Likewise.
* pfinet/linux-src/net/ipv4/fib_hash.c: Likewise.
* pflocal/connq.c: Likewise.
* pflocal/socket.c: Likewise.
|
|
* libdiskfs/name-cache.c (struct lookup_cache): Fix type of
dir_cache_id, node_cache_id.
|
|
* pfinet/linux-src/include/net/addrconf.h: Include ipv6.h.
|
|
* exec/exec.c: Include mach/gnumach.h.
* exec/main.c: Include device/device.h.
|
|
* libdiskfs/diskfs.h (struct peropen): Use refcount_t for field refcnt.
* libdiskfs/peropen-make.c (diskfs_make_peropen): Initialize refcnt.
* libdiskfs/peropen-rele.c (diskfs_release_peropen): Adjust accordingly.
* libdiskfs/protid-make.c (diskfs_start_protid): Likewise. Also, the
node must no longer be locked, adjust comment accordingly.
(diskfs_create_protid): Likewise.
|
|
* include/Makefile (installhdrs): Add refcount.h.
|
|
As of recently, fakeroot would fail to create symlinks:
% fakeroot-hurd ln -s foo a
ln: failed to create symbolic link ‘a’: Operation not permitted
Fix this by overriding fshelp_isowner.
Various netfs functions will call fshelp_isowner to check whether USER
is allowed to do some operation. As fakeroot is not running within
the fakeauth'ed environment, USER contains the real user.
I have no explanation why this ever worked.
* trans/fakeroot.c (fshelp_isowner): New function.
|
|
* include/refcount.h: New file.
|
|
* libihash/ihash.c (hurd_ihash_add): Move the code computing the load
factor of the hash table...
* libihash/ihash.h (hurd_ihash_get_load): ... here, together with the
comment describing the method and the rationale for chosing binary
percent.
|
|
* libihash/ihash.c (hurd_ihash_add): Fix typo.
|
|
* proc/hash.c (reqport_find): Move this function...
* proc/proc.h (process_drop): ... and this...
* proc/mig-decls.h: ... here and rename them.
* proc/mig-mutate.h: Update accordingly.
|
|
* trans/fakeroot.c (main): Use C99-style struct initialization to
initialize argp. This avoids a warning about missing field
initializers.
|
|
* trans/fakeroot.c (netfs_attempt_chown): Fix comparison between
signed and unsigned integer expressions.
|
|
A spurious semicolon caused a control flow bug in check_openmodes,
leading to a port leak.
* trans/fakeroot.c (check_openmodes): Remove spurious semicolon.
|
|
Expressing the maximum load in binary percent (where 128b% corresponds
to 100%) allows us to use fast binary scaling to determine if the
maximum load has been reached without losing precision.
Furthermore, the previously used expression 'ht->nr_items * 100'
overflows int at 2^25 (unsigned int at 2^26). When a hash table
reached that limit, it would fail to resize and fill up the table.
This change fixes that.
* libihash/ihash.c (hurd_ihash_set_max_load): Update the comment.
(hurd_ihash_add): Use fast binary scaling to determine the current
load.
* libihash/ihash.h (struct hurd_ihash): Update comment for max_load.
(hurd_ihash_set_max_load): Update the comment.
|
|
libihash uses open addressing. Previously, quadratic probing in both
directions was used to resolve collisions. Quadratic probing might
result in a less efficient use of caches.
Also, prime numbers of the form 4 * i + 3 were used as array sizes.
This was used in combination with the integer modulo operation for
hashing. It has been known for some time that libihash suffers from
collisions, so a integer hash function is now applied to the keys to
derive the index.
Use linear probing instead. Also, use powers of two for the array
sizes, so a bit mask can be used for the modulo operation.
* libihash/ihash.c (ihash_sizes, ihash_nsizes): Remove.
(find_index): Use linear probing and fast modulo operation.
(add_one): Likewise.
* libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro.
|
|
Use an integer hash function to derive the index from the key. This
should reduce the number of collisions.
* libihash/ihash.c (hash_int32): New function.
(find_index): Use hash_int32 on the key to derive the index.
(add_one): Likewise.
|
|
Previously, int was used for the field max_load of struct hurd_ihash.
There is no reason for this as far as I can tell. Furthermore,
hurd_ihash_set_max_load takes an unsigned int max_load.
* libihash/ihash.h (struct hurd_ihash): Use unsigned int for field
max_load.
|
|
The performance of hash tables depend critically on a low number of
hash collisions. As the table fills up, the chance of collisions
necessarily raises.
Previously, libihash resized the hash table when the load exceeded
80%. This seems a bit optimistic (e. g. java.util.Hashtable uses 75%
as default).
* libihash/ihash.h (HURD_IHASH_MAX_LOAD_DEFAULT): Set to 75.
|
|
Previously, the superblock was mmaped and a pointer stored in sblock
by map_hypermetadata. This memory is backed by our disk pager.
This is rather unfortunate, as this means that whenever we read a
value from that location, we might generate a request our disk pager.
This amplifies the so-called thread-storm problem.
Rather than relying on a mmaped region of memory, just use the data
loaded by get_hypermetadata.
* ext2fs/hyper.c (get_hypermetadata): Do not free sblock.
(mapped_sblock): New variable.
(map_hypermetadata): Map the superblock to mapped_sblock instead.
(diskfs_set_hypermetadata): Copy superblock into mapped_superblock.
* ext2fs/ext2fs.h (get_hypermetadata, map_hypermetadata): Adjust
comments accordingly.
|
|
fatfs has two kinds of pagers. One for the files, one for the disk.
Previously, both were in the same port bucket.
If a request for a file pager arrives, it most likely touches some
metadata (like the superblock). This is in turn backed by the disk
pager, so another request is generated for the disk pager.
Seperate all pagers clearly by using two port buckets. This will
enable us to use a single thread per port bucket in the future.
* fatfs/pager.c (pager_bucket): Rename to...
(disk_pager_bucket): ... this to make the change explicit at every
occurrence.
(file_pager_bucket): New variable.
(service_paging_requests): New function.
(create_fat_pager): Also create the file pager.
(diskfs_get_filemap): Handout pagers from the file_pager_bucket.
(diskfs_shutdown_pager): This is only concerned with the file pager.
Simplify code accordingly.
(diskfs_sync_everything): Likewise.
(diskfs_pager_users): Likewise.
(diskfs_max_user_pager_prot): Likewise.
(disable_caching): Iterate over both buckets.
(enable_caching): Likewise.
|
|
* libports/bucket-iterate.c (_ports_bucket_class_iterate): Unlock
_ports_lock on malloc failure.
|
|
ext2fs has two kinds of pagers. One for the files, one for the disk.
Previously, both were in the same port bucket.
If a request for a file pager arrives, it most likely touches some
metadata (like the superblock). This is in turn backed by the disk
pager, so another request is generated for the disk pager.
Seperate all pagers clearly by using two port buckets. This will
enable us to use a single thread per port bucket in the future.
* ext2fs/pager.c (pager_bucket): Rename to...
(disk_pager_bucket): ... this to make the change explicit at every
occurrence.
(file_pager_bucket): New variable.
(service_paging_requests): New function.
(create_disk_pager): Also create the file pager.
(diskfs_get_filemap): Handout pagers from the file_pager_bucket.
(diskfs_shutdown_pager): This is only concerned with the file pager.
Simplify code accordingly.
(diskfs_sync_everything): Likewise.
(diskfs_pager_users): Likewise.
(diskfs_max_user_pager_prot): Likewise.
(disable_caching): Iterate over both buckets.
(enable_caching): Likewise.
|
|
Currently, diskfs_node_iterate iterates twice over all nodes. The
first time only to determine the number of nodes. Simply count them
instead.
* tmpfs/node.c (all_nodes_nr_items): New variable.
(diskfs_free_node): Decrement all_nodes_nr_items.
(diskfs_node_norefs): Likewise.
(diskfs_cached_lookup): Increment all_nodes_nr_items.
(diskfs_node_iterate): Fix type of sum_nodes, use all_nodes_nr_items.
|
|
Currently, diskfs_node_iterate iterates twice over all nodes in the
cache. The first time only to determine the number of nodes currently
in the cache. Simply count them instead.
* fatfs/inode.c (nodehash_nr_items): New variable.
(diskfs_cached_lookup): Increment nodehash_nr_items.
(diskfs_cached_lookup_in_dirbuf): Likewise.
(diskfs_node_norefs): Decrement nodehash_nr_items.
(diskfs_node_iterate): Fix the type of num_nodes, use nodehash_nr_items.
|
|
Currently, diskfs_node_iterate iterates twice over all nodes in the
cache. The first time only to determine the number of nodes currently
in the cache. Simply count them instead.
* ext2fs/inode.c (nodehash_nr_items): New variable.
(diskfs_cached_lookup): Increment nodehash_nr_items.
(diskfs_node_norefs): Decrement nodehash_nr_items.
(diskfs_node_iterate): Fix the type of num_nodes, use nodehash_nr_items.
|
|
* fatfs/pager.c (add_pager_max_prot): Simplify expression.
|
|
_ports_bucket_class_iterate creates a snapshot of the buckets hash
table. This is done so that the lock protecting the hash table can be
released while we iterate over the snapshot.
Formerly, a linked list was used to store the snapshot. As the
maximal number of items is known, using an array is much simpler.
_ports_bucket_class_iterate implements both ports_bucket_iterate and
ports_class_iterate. For this change might make ports_class_iterate
less efficient memory-wise if the number of ports belonging to the
class is low with respect to the number of ports in the bucket. If
this happens, we allocate too much. Alleviate this by releasing
unused memory.
On the other hand, the array representation is more compact.
Furthermore a survey of the Hurd code revealed that
ports_class_iterate is rarely used, while ports_bucket_iterate is used
more often, most prominently in paging code.
* libports/bucket-iterate.c (_ports_bucket_class_iterate): Use an
array instead of a linked list.
|
|
* ext2fs/pager.c (add_pager_max_prot): Simplify expression.
|
|
Previously, inum was of type int, whereas dino_ref expects ino_t. On
Hurd/x86 the former is 32 bit wide, the latter 64. If dino_ref is
inlined, this does not seem to pose a problem, but if ext2fs is
compiled with -O0, this most likely results in an invalid memory access.
* ext2fs/ialloc.c (ext2_alloc_inode): Use type ino_t for inum.
|
|
* exec/exec.c (do_exec): If the formatted task name exceeds
TASK_NAME_SIZE, abbreviate it.
|
|
Some servers use ports_manage_port_operations_one_thread to process
requests and terminate when it returns. Since many of them don't detach
before shutting down, a client may receive an error if its request
arrived while the server is shutting down. Prevent those spurious errors
by forcing ports_manage_port_operations_one_thread not to return.
This is the same change as 235491231bdd1fd93507c835767503f047e10b91
introduced for ports_manage_port_operations_multithread.
* libports/manage-one-thread.c
(ports_manage_port_operations_one_thread): Force timeout to 0.
|
|
The default sync interval has been changed in 9e55fdd7 from 30 to 5
seconds. This change was not reflected in the documentation.
At least for current hardware, using 30 seconds instead of just 5
alleviates the thread-storm problem. Make 30 seconds the default
again.
* libdiskfs/priv.h (DEFAULT_SYNC_INTERVAL): Set to 30 seconds.
|
|
following 7cb7fa6b3a0d02985b4a51f7823bc1cb631d6bfa
* proc/mgt.c (S_proc_exception_raise): Do not dereference e on returning
EINVAL, the translation functions does it for us.
|
|
|
