On Tue, 1 Aug 2000 13:38:16 +0100 (BST),
Mark Hemment <markhe@veritas.com> wrote:
> I've attached a patch (against 2.4.0-test5) for the page cache, which
>demonstrates a technique to reduce the length of re-searching of a chain
>after its guarding lock has been temporarily dropped (say, for a blocking
>operation), and the re-search is expected to fail.
>[snip]
> By inserting a marker (cookie) as the first object (after the original
>search and while the guarding lock is still held) gives a well known
>point at which to terminate a subsequent search (assuming it doesn't match
>before reaching the marker).
>[snip]
There is a method which may give almost the same performance boost but
is much easier to use. Associate an update counter with each chain
head. Every add or delete on that chain increments the counter, the
lock is held so no need for atomic_t counters. If the chain head is
being updated at the same time then the counter update is almost free,
assuming the head and the counter are in the same cache line.
The sequence is then :-
start:
get_lock();
search_chain();
if (entry not found) {
save_chain_update_counter();
drop_lock();
allocate_new_object();
format_new_object();
get_lock();
If (current_chain_counter != saved_chain_counter) {
drop_lock();
free_new_object();
goto start;
}
insert_object();
++chain_counter();
}
entry_exists_do_something:
The cost is obviously one extra word per chain head. The benefit is
that the algorithm is completely independent of the data on the chain.
Assuming the common case is no updates to this chain while the lock was
released, it removes the second scan of the chain.
Freeing the new object on restart simplifies the code, no need to
remember if you already have a pre-formatted object and no need to free
any pre-formatted object if the entry exists on the second pass. OTOH,
if the overhead of freeing is too high (which depends on the frequency
of concurrent updates) then more complex code could be used to remember
any pre-formatted object.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Mon Aug 07 2000 - 21:00:05 EST