Project

General

Profile

Bug #2669

DJB hash collision for stats cache

Added by pansa over 3 years ago. Updated over 3 years ago.

Status:
Fixed
Priority:
Normal
Assignee:
-
Category:
core
Target version:
Start date:
2015-09-15
Due date:
% Done:

100%

Estimated time:
Missing in 1.5.x:

Description

Hi!
We use lighttpd for our product components update. The components - are few handreds files with similar names, like:

drw70000.vdb
drw70001.vdb
drw70002.vdb
drw70003.vdb
drw70004.vdb
drw70005.vdb
drw70006.vdb
drw70007.vdb
drw70008.vdb
drw70009.vdb
...
drw700c2.vdb
drw700c3.vdb
drw700c4.vdb
drw700c5.vdb
drw700c6.vdb

(radix digit+alfa index naming)

Http client requests all files in filename order, and one day we get a strange problem - one (and only one!) file recieved not whole, but get http 200!
We discover problem and found lighttpd hash collision for caching file stats. In sources we found DJB hash using, and for our DIFFERENT filenames its return same value :

hash(drw700c0.vdb) 1750305894
hash(drw700ar.vdb) 1750305894

Set server.stat-cache-engine to disable resolve our problem, but may be you found other way to improve caching.

lighttpd/1.4.35

Associated revisions

Revision 3039 (diff)
Added by stbuehler over 3 years ago

[stat-cache] fix handling of collisions, might have returned wrong data (fixes #2669)

- don't remember splay_tree nodes for long (dir_node, file_node) after
cache lookup; only remember the data they pointed to (sce for file
entries, fam_node for dir entries)
- unset sce / fam_node when a collision (not matching path) is detected
- check again for collision before splaytree_insert; the entry in
question is already at the top because it was splayed before. simply
replace the data on collisions (and release the old data).
- check fam_node for collisions too
- splaytree_size handles NULL nodes too
- enable some force_assert lines (were in #ifdef DEBUG_STAT_CACHE before)

Differential Revision: https://review.lighttpd.net/D1

From: Stefan Bühler <>

Revision 69f890e2 (diff)
Added by stbuehler over 3 years ago

[stat-cache] fix handling of collisions, might have returned wrong data (fixes #2669)

- don't remember splay_tree nodes for long (dir_node, file_node) after
cache lookup; only remember the data they pointed to (sce for file
entries, fam_node for dir entries)
- unset sce / fam_node when a collision (not matching path) is detected
- check again for collision before splaytree_insert; the entry in
question is already at the top because it was splayed before. simply
replace the data on collisions (and release the old data).
- check fam_node for collisions too
- splaytree_size handles NULL nodes too
- enable some force_assert lines (were in #ifdef DEBUG_STAT_CACHE before)

Differential Revision: https://review.lighttpd.net/D1

From: Stefan Bühler <>

git-svn-id: svn://svn.lighttpd.net/lighttpd/branches/lighttpd-1.4.x@3039 152afb58-edef-0310-8abb-c4023f1b3aa9

History

#1

Updated by stbuehler over 3 years ago

  • Status changed from New to Fixed
  • % Done changed from 0 to 100

Applied in changeset r3039.

#2

Updated by stbuehler over 3 years ago

  • Category set to core
  • Target version set to 1.4.38

Hi, thanks for reporting. I think it was broken independent of the server.stat-cache-engine setting, but maybe it's harder to trigger.

Anyway, now old entries are replaced on collisions, and there is no attempt to reuse old data.

Also available in: Atom