openSUSE (including Leap, Tumbleweed, Open Build Services, openQA, YaST)
A use case of Patricia-tree: MIB retrieving
I'm a software engineer who is a member of Joey Lee's team. My major job in this team is shim module maintenance.
No video of the event yet, sorry!
In SuSE* Linux, MIB files are located in /usr/share/snmp/mibs. User can install MIB by zipper install snmp-mibs-x.x.x.x. In Data Center, OS running in server must quickly interpret trap information from BMC, and must reply any request from outside world for MIB.
Patricia tree developed from a compressed binary trie is one of the famous longest search algorithm. For example, it has been popularly deployed in core router for IPv6 table searching. Each element node has a bit-number, either 0 or 1, to let search algorithm decide which target bit should be compared. If the compared bit value is 0, it then goes to left child, otherwise, it continuously goes to right sibling. Unlike Binary trie, those unused element nodes can be eliminated in Patricia Tree. This is why we insist Patricia tree can save memory resources for MIB parsing in the system initial phase. Nevertheless, all search algorithms of Binary trie, actually it is a binary tree internally, are still highly adaptive for Patricia.
My solution
1.Scramble each object id to ASCII code, and concaternate all of object id together to create a bit string. 2.Build a normal binary tree 3.Eliminate degree one nodes 4.Calculate decision bit number for each node 5.replace/combine empty node with value node
NODE *patricia_get(char oid, NODE *cur, NODE *parent) { while(TRUE) db = (oid >> (OID_BIT_NUM - cur->db)) & 0x01; if (cur->db > parent->db) parent = cur; if (db is equal to 0) cur = cur->left; else cur = cur->right; else break; return cur; }
- Date:
- 2023 October 21 - 10:15
- Duration:
- 15 min
- Room:
- A112
- Conference:
- openSUSE.Asia Summit 2023
- Language:
- Track:
- Main Track
- Difficulty:
- Easy
- SELinux introduction
- Start Time:
- 2023 October 21 10:15
- Room:
- A108
- openSUSE running on RISC-V
- Start Time:
- 2023 October 21 10:15
- Room:
- A109