Suricata

1. Finds the first node A greater than or equal to the offset
2. Find A's prev node B
3. Check B->len+B->offset > offset? yes:return B ,no: return A

According to optimization above, we've decrease the cpu time from 8-12% to under 1%.

chris tang wrote in #note-1:

1. Finds the first node A greater than or equal to the offset
2. Find A's prev node B
3. Check B->len+B->offset > offset? yes:return B ,no: return A

According to optimization above, we've decrease the cpu time from 8-12% to under 1%.

Thank you.
Q: Could you please tell how is it guaranteed that only the A's prev node B will satisfy B->len + B->offset > offset?
Q: Could it not be any other node prior to A?

Shivani Bhardwaj wrote in #note-2:

chris tang wrote in #note-1:

1. Finds the first node A greater than or equal to the offset
2. Find A's prev node B
3. Check B->len+B->offset > offset? yes:return B ,no: return A

According to optimization above, we've decrease the cpu time from 8-12% to under 1%.

Thank you.
Q: Could you please tell how is it guaranteed that only the A's prev node B will satisfy B->len + B->offset > offset?
Q: Could it not be any other node prior to A?

Thanks for pointing out that, that's also confused me.
So I read the SBBUpdate function code, found that new StreamingBufferBlock node will be adjusted by ConsolidateFwd and ConsolidateBackward to make sure there is only one node at a certain offset+len, overlap would be merged, only gap exists? I'm not sure if my understanding is right. If it is,i think any node prior to B will not satisfy if B satisfied B->len + B->offset > offset ?

So I read the SBBUpdate function code, found that new StreamingBufferBlock node will be adjusted by ConsolidateFwd and ConsolidateBackward to make sure there is only one node at a certain offset+len, overlap would be merged, only gap exists? I'm not sure if my understanding is right. If it is,i think any node prior to B will not satisfy if B satisfied B->len + B->offset > offset ?

Thank you for the necessary pointers. Apologies for getting back late on this.
After my analysis, I think you algorithm could actually work and yield more correct results indeed.
However, I'm a bit unsure about the claimed time complexity of the rbtree macros. It seems to me that RB_NEXT (finding successor) will take the same amount of time as RB_PREV (finding predecessor) i.e. O(lg n) per run. Please check the implementation in tree.h in the source code. Lmk wdyt about this?

However, with the change in algorithm that you suggest, particularly the search for first node greater than equal to offset, we always seem to reach the correct node.

I'd like to understand how you'd handle the following.
Assumption: There is no offset bigger than the current offset in the tree.
1. There does exist an overlap with an existing buffer whose offset + len > offset (right most node always?)
2. There is no block covering that offset (so, perhaps we're in a GAP?)

Let's see if your PR passes our QA and if our analysis is correct. :) Please make sure to add your test results and useful pointers/test data for us to verify that as well.

Please feel free to assign the ticket to yourself since you're working on it. Thanks.

chris tang wrote in #note-6:

Thank you for your ongoing attention and responses to my tickets.

However, I'm a bit unsure about the claimed time complexity of the rbtree macros. It seems to me that RB_NEXT (finding successor) will take the same amount of time as RB_PREV (finding predecessor) i.e. O(lg n) per run. Please check the implementation in tree.h in the source code. Lmk wdyt about this?

Sorry for my describe, yes the time complexity of RB_NEXT is equal to RB_PREV, i mean, but the GetBlock call O(n) times RB_NEXT.

ah ok. yes, thank you!

[...]

It searches from beginning of the tree, one by one, truns rb tree search into line. In worst situation, the node we find is the end block of the streaming buffer, it takes n*logn time to find it. If we find the prior node from root, we can run RB_PREV only once. Here's the code snippet:

agreed.

[...]

However, with the change in algorithm that you suggest, particularly the search for first node greater than equal to offset, we always seem to reach the correct node.

I'd like to understand how you'd handle the following.
Assumption: There is no offset bigger than the current offset in the tree.
1. There does exist an overlap with an existing buffer whose offset + len > offset (right most node always?)
2. There is no block covering that offset (so, perhaps we're in a GAP?)

Pleas look at the code snippet,
1.Return the RB_MAX node, then check if it satisfied offset and length check
2.Like what current GetBlock code is doing: seems that there is't a correct node, so we return NULL.

Let's see if your PR passes our QA and if our analysis is correct. :) Please make sure to add your test results and useful pointers/test data for us to verify that as well.

Please feel free to assign the ticket to yourself since you're working on it. Thanks.

Thanks,here's the commit https://github.com/regit/suricata/pull/51/commits/04906b57fdb0ed5a941389e8630c7783cd15d740 PR and hope it passed the QA.

Thank you. Could you please create a PR at https://github.com/OISF/suricata/ so we can see if the QA passes and we're both correct in our analysis? ;)

Shivani Bhardwaj wrote in #note-7:

Thank you. Could you please create a PR at https://github.com/OISF/suricata/ so we can see if the QA passes and we're both correct in our analysis? ;)

Oh sorry for my mistake. I've request a PR at https://github.com/OISF/suricata/ but wrote the wrong address, here's the PR https://github.com/OISF/suricata/pull/11727, and i'm requesting a new PR to format code and sign commit.
Thanks.

Here is the new PR https://github.com/OISF/suricata/pull/11749