[Bro-Dev] [JIRA] (BIT-1043) LRU Table implementation

[Jordi Ros-Giralt (JIRA)]

Jordi Ros-Giralt created BIT-1043:
-------------------------------------

             Summary: LRU Table implementation
                 Key: BIT-1043
                 URL: https://bro-tracker.atlassian.net/browse/BIT-1043
             Project: Bro Issue Tracker
          Issue Type: Improvement
          Components: Bro
    Affects Versions: 2.1
            Reporter: Jordi Ros-Giralt
            Priority: Medium


Attaching below the email description i exchanged with Seth and Robin describing this work.
------
Hi Seth and Robin,

We got the repo up, you can get to our branch as follows:

git clone --recursive https://github.com/giralt/bro.git
cd bro/
git checkout lru-table

We would be happy to contribute this code to the Bro community.  This is what it does:

- It implements LRU tables for Bro
- A Bro table can be enhanced with the LRU functionality with the following new table attributes:

&lru_table: enhance the table with LRU functionality

&size_limit=n: if adding an element to the table makes the size of the table larger than n, then drop the LRU element from that table before inserting the new element.  n=0 means table size can be infinite (so don't drop elements from it)

&drop_func=callback_func: defines a programmable callback function that gets called automatically every time an element from the LRU table is dropped due to hitting the size_limit.  The prototype of this callback must be as follows:

function callback_func(t: table[keytype] of valuetype, key: keytype, val: valuetype): count

- It adds the following bif functions:

function get_lru%(v: any%): any
function get_mru%(v: any%): any
function get_lru_key%(v: any%): any
function get_mru_key%(v: any%): any

- Example:

function freed(t: table[port] of string, key: port, val: string): count { print "Dropped"; }
local port_names: table[port] of string &lru &size_limit=2 &drop_func=freed;

In terms of applications, we are currently using this feature for the chimera-to-bro compiler we are working on: http://www.chimera-query.org/index.html

We thought that we could also use this feature to provide a sort of memory management facility for Bro.  I had a talk with Seth some weeks ago about this.  Something like the LRU implementation allows programmers to put bounds on the size of tables and prioritize which elements can be dropped first upon memory exhaustion scenarios.  Perhaps an idea here would be to develop a garbage collector (could be done using Bro language itself, perhaps as a framework) which would be run upon hitting a certain memory usage watermark and which would mainly run through the set of tables marked as "garbage collectable" dropping LRU elements from them to help reduce/eliminate the risk of running out of memory.

Should this be something interesting, what are the steps we would need to do to open source the LRU code into Bro?


--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://bro-tracker.atlassian.net/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira