diff options
author | Guy Harris <guy@alum.mit.edu> | 2017-03-03 20:34:59 -0800 |
---|---|---|
committer | Guy Harris <guy@alum.mit.edu> | 2017-03-04 04:35:42 +0000 |
commit | b7e9582fd72d85373d5223394d55f405edd0eca8 (patch) | |
tree | f17aadfd8584287016fd66ef171f499d05db2952 /epan/frame_data_sequence.c | |
parent | 59bbe6b0cd4f33341c5c0a517474debf579b6804 (diff) |
Fix the calculation of the number of levels in the radix tree.
The algorithm being used calculated the number of levels in a
1024-leaf-node tree as being 2, but it's 1 - 0 elements means 0 levels,
1 through 1024 elements means 1 level, 1025 through 1024^2 elements
means 2 levels, etc.. With a count of 1024, the loop would bump the
level count from 0 to 1, and divide the element count by 1024, yielding
1, so the loop would not terminate, and the level count would them go
from 1 to 2 and the element count would go to 0.
This could cause problems if exactly 1024 packets were seen.
Just use an if chain, similar to the one used when adding elements to
the tree.
Bug: 13433
Change-Id: I3eaeaf374bb65b37b38a59e95f77cac6690614ed
Reviewed-on: https://code.wireshark.org/review/20379
Reviewed-by: Guy Harris <guy@alum.mit.edu>
Diffstat (limited to 'epan/frame_data_sequence.c')
-rw-r--r-- | epan/frame_data_sequence.c | 24 |
1 files changed, 19 insertions, 5 deletions
diff --git a/epan/frame_data_sequence.c b/epan/frame_data_sequence.c index a2e56006f4..af237e807c 100644 --- a/epan/frame_data_sequence.c +++ b/epan/frame_data_sequence.c @@ -291,13 +291,27 @@ free_frame_data_array(void *array, guint count, guint level, gboolean last) void free_frame_data_sequence(frame_data_sequence *fds) { - guint32 count = fds->count; - guint levels = 0; + guint levels; /* calculate how many levels we have */ - while (count) { - levels++; - count >>= LOG2_NODES_PER_LEVEL; + if (fds->count == 0) { + /* The tree is empty; there are no levels. */ + levels = 0; + } else if (fds->count <= NODES_PER_LEVEL) { + /* It's a 1-level tree. */ + levels = 1; + } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 2-level tree. */ + levels = 2; + } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 3-level tree. */ + levels = 3; + } else { + /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4 + 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10, + so fds->count is always less < NODES_PER_LEVEL^4. */ + /* It's a 4-level tree. */ + levels = 4; } /* call the recursive free function */ |