Project

General

Profile

Actions

Optimization #4747

open

app-layer: make tx iterator a mandatory part of the API

Added by Victor Julien about 3 years ago. Updated over 1 year ago.

Status:
New
Priority:
Normal
Assignee:
Target version:
Effort:
Difficulty:
Label:

Subtasks 1 (0 open1 closed)

Optimization #4748: app-layer/rust: explore if tx iterator can be implemented as a traitClosedJason IshActions

Related issues 2 (0 open2 closed)

Related to Suricata - Bug #4741: Quadratic complexity in modus due to missing tx_iteratorClosedPhilippe AntoineActions
Related to Suricata - Bug #5314: ftp: quadratic complexity for tx iterator with linked listClosedPhilippe AntoineActions
Actions #1

Updated by Victor Julien about 3 years ago

  • Related to Bug #4741: Quadratic complexity in modus due to missing tx_iterator added
Actions #2

Updated by Philippe Antoine about 3 years ago

Maybe a macro would be easier as export_tx_data_get or such

A trait would need to be implemented for each State structure with a function returning an iterator over a list of Transactions traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)

Actions #3

Updated by Jason Ish about 3 years ago

Why make it a mandatory part of the API? I think it should be in the description? Simply to avoid performance issues?

Actions #4

Updated by Jason Ish about 3 years ago

Philippe Antoine wrote in #note-2:

Maybe a macro would be easier as export_tx_data_get or such

A trait would need to be implemented for each State structure with a function returning an iterator over a list of Transactions traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)

First we'd just make the iterator non-optional in the parser registration on the Rust side, at least forcing a C binding to be created.

But I think a generic function will take care of this without the overhead of a trait. Last I tried using traits on the actual parser object I hit up against some FFI issues with trait pointers, probably worth revisiting, but for this, I think a generic utility functions is all thats needed.

Create a trait, Transaction that exposes a get_id method and implement this for each ProtocolTransaction struct. Then we can make a utility function that is generic over Transaction, something like:

fn get_iter<'a, T: Transaction>(transactions: &'a[T], min_tx_id: u64, state: &mut u64) -> Option<(&'a T, u64, bool)> {
    let mut index = *state as usize;
    let len = transactions.len();
    while index < len {
        let tx = &transactions[index];
        if tx.get_id() < min_tx_id + 1 {
            index += 1;
            continue;
        }
        *state = index as u64;
        return Some((tx, tx.get_id() - 1, (len - index) > 1));
    }
    None
}
Actions #6

Updated by Jason Ish about 3 years ago

Philippe Antoine wrote in #note-2:

Maybe a macro would be easier as export_tx_data_get or such

A trait would need to be implemented for each State structure with a function returning an iterator over a list of Transactions traits which can return an id
I do not know if it has performance implications (like type assertions at runtime, or more memory...)

If you can avoid dynamic dispatch then generally the performance hit happens at compile time rather than runtime. If you see my PR (https://github.com/OISF/suricata/pull/6519) the traits specify behaviour where the function call overhead will be erased after optimization, then the generic function uses static dispatch for the generic functions, meaning its acting more like a macro with a separate implementation being generated and compiled for each type. So I think we can do this without worrying about runtime performance overhead.

Actions #7

Updated by Jason Ish over 2 years ago

  • Related to Bug #5314: ftp: quadratic complexity for tx iterator with linked list added
Actions #8

Updated by Philippe Antoine over 1 year ago

  • Assignee set to OISF Dev
  • Target version set to 8.0.0-beta1

Only SSH seems to have None (and it has ever only one transaction)

Actions

Also available in: Atom PDF