Wireshark mailing list archives
Is this the bug of wmem_tree_lookup32_array_le()?
From: "qiangxiong.huang via Wireshark-dev" <wireshark-dev () wireshark org>
Date: Sun, 17 Oct 2021 17:40:34 +0800
I investigate the issue https://gitlab.com/wireshark/wireshark/-/issues/17633, and find that the bug is caused by using wmem_tree_lookup32_array_le(). HTTP2 streaming mode reassembly need to store reassembly information indexed by http2 frame number (as the key), and look up the information that has the largest key that is less than or equal to the search key (http2 frame number) while handling other http2 frames later. The wmem_tree_insert32() and wmem_tree_lookup32() provides similar functions. But the http2 frame number is type of guint64. Since there is no function like wmem_tree_lookup64(), I use wmem_tree_insert32_array() and wmem_tree_lookup32_array_le() instead. The key is guint32[2], key[0] is the higher 32 bits of a http2 frame number, key[1] is the lower 32 bits. But I find wmem_tree_lookup32_array_le() does not work as I thought. For example, there are two http2 frames with frame numbers 0x1200000008 and 0x1400000001. In guint32 arrays the first frame number is [0x12, 0x08] and the second is [0x14, 0x01]. Storing the data of the first http2 frame data like: (note following pseudo code ignored the struct of wmem_tree_key_t) wmem_tree_insert32_array(tree, [0x12, 0x08], data); Then try to find the data of first frame during handling the second http2 frame: wmem_tree_lookup32_array_le(tree, [0x14, 0x01]); But it will return NULL. Because the behavior of wmem_tree_lookup32_array_le() is that it will check all keys in order: 1. First, wmem_tree_lookup32_array_le() matchs the node in the branch which storing the data of first frame because 0x12 < 0x14; 2. But it continues to compare 0x08 > 0x01, then return NULL because there is no key less than or equal to 0x01. As I expected, if there is a key of a node of branch less than search key (0x12 < 0x14), the node of branch (or leaf) with max key must be returned without checking remaining keys in order. For example, if a data with key [0x02, 0x03, 0x15] stored in the tree. The data should be return if look up with key like [0x04, 0x01, 0x00], [0x02, 0x04, 0x01] or [0x02, 0x03, 0x16], and should not be returned if look up with key [0x01, 0x05, 0x04], [0x02, 0x02, 0x17] or [0x02, 0x03, 0x14]. Who knows that the current behavior of the wmem_tree_lookup32_array_le() is designed in this way or it is just a bug? If I want to fix the issue #17633, should I modify this wmem_tree_lookup32_array_le() directly or write a new function like wmem_tree_lookup32_array_le_key_as_big_num() (or other name you recommend)?
___________________________________________________________________________ Sent via: Wireshark-dev mailing list <wireshark-dev () wireshark org> Archives: https://www.wireshark.org/lists/wireshark-dev Unsubscribe: https://www.wireshark.org/mailman/options/wireshark-dev mailto:wireshark-dev-request () wireshark org?subject=unsubscribe
Current thread:
- Is this the bug of wmem_tree_lookup32_array_le()? qiangxiong.huang via Wireshark-dev (Oct 17)
- Re: Is this the bug of wmem_tree_lookup32_array_le()? John Thacker (Oct 19)
- <Possible follow-ups>
- Re: Is this the bug of wmem_tree_lookup32_array_le()? qiangxiong.huang via Wireshark-dev (Oct 19)
- Re: Is this the bug of wmem_tree_lookup32_array_le()? John Thacker (Oct 19)