When I was in college, I knew about the database, heard the teacher talk about the line-level lock, and I had this concept in my mind. I didn't see the source code, nor did I realize it. When I read the suricata source code last year, I happened to see the hash row lock by chance. I felt an inexplicable impulse and felt that this should be the famous lock. Look at the code implementation with excitement. To explain why suricata uses row locks, suricata develops a multi-threaded architecture to process data packets concurrently, because it can't make good use of the disadvantages of multi-core cpu. Many data are shared between threads, so row-level lock hash tables are used in many places. The first place where line locks are used is the connection management module (hash table, retrieval speed O(1)
This source code version is 3.0.1, official website: https://suricata-ids.org/
Hash table for connection management: FlowBucket *flow_hash. It is a chain hash table, which is defined as followstypedef struct FlowBucket_ {
Flow *head; /* Chain Headers*/
Flow *tail;/* End of list*/
/* Line Lock Type*/
#ifdef FBLOCK_MUTEX
SCMutex m;
#elif defined FBLOCK_SPIN
SCSpinlock s;
#else
#error Enable FBLOCK_SPIN or FBLOCK_MUTEX
#endif
} __attribute__((aligned(CLS))) FlowBucket;
typedef struct Flow_
{
...
/* Node locks to improve concurrency*/
#ifdef FLOWLOCK_RWLOCK
SCRWLock r;
#elif defined FLOWLOCK_MUTEX
SCMutex m;
#else
#error Enable FLOWLOCK_RWLOCK or FLOWLOCK_MUTEX
#endif
...
/* A bidirectional linked list composed of hnext hprev */
/** hash list pointers, protected by fb->s */
struct Flow_ *hnext; /* hash list */
struct Flow_ *hprev;
...
} Flow;flow_hash is an array, and each FlowBucket element consists of head, tail, and hnext, hprev of flow to form a bidirectional list, which is called row. The number of rows for this hash is determined by the configuration file or default value (flow_config.hash_size)
The code is as follows:
flow_hash = SCCalloc(flow_config.hash_size, sizeof(FlowBucket));
The interface is as follows:
FlowGetFlowFromHash: Get a connection from the information of the packet, and create a flow if it is not in the hash table.
FlowLookup FlowFromHash: Find connections through the information of the packet, and do not create them;
If the return of the above two functions is successful, the node will be locked and protected, which is also used for concurrent access.
The source code is as follows:
Flow *FlowGetFlowFromHash(ThreadVars *tv, DecodeThreadVars *dtv, const Packet *p)
{
Flow *f = NULL;
FlowHashCountInit;
/* get the key to our bucket */
uint32_t hash = FlowGetHash(p); /* Hash value of connection*/
/* get our hash bucket and lock it */
FlowBucket *fb = &flow_hash[hash % flow_config.hash_size]; /* Locate the corresponding row according to the hash value of the connection*/
/* This is the key point, which is to lock this line (linked list) code, rather than the entire hash table, can improve concurrency. */
FBLOCK_LOCK(fb);
SCLogDebug("fb %p fb->head %p", fb, fb->head);
FlowHashCountIncr;
/* see if the bucket already has a flow */
if (fb->head == NULL) {
/* If the empty row of the hash table indicates that there are no elements in the list, a flow node is obtained. If the node returns successfully, the node is locked by the node, then initialized, and the row lock is unlocked before returning.*/
f = FlowGetNew(tv, dtv, p);
if (f == NULL) {
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return NULL;
}
/* flow is locked */
fb->head = f;
fb->tail = f;
/* got one, now lock, initialize and return */
FlowInit(f, p);
f->flow_hash = hash;
f->fb = fb;
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Row lock unlocking */
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return f;
}
/* ok, we have a flow in the bucket. Let's find out if it is our flow */
/* If the row has elements, traverse the list to find the corresponding flow*/
f = fb->head;
/* see if this is the flow we are looking for */
/* Whether the first element of the line is the flow to look for, 0 means no, 1 means yes*/
if (FlowCompare(f, p) == 0) {
Flow *pf = NULL; /* previous flow */
/* Traverse the list to find the flow corresponding to the package. If not, call FlowGetNew to create, and the rest is basically the same as the code above.*/
while (f) {
FlowHashCountIncr;
pf = f;
f = f->hnext;
if (f == NULL) {
/*If the call succeeds, the node locks */
f = pf->hnext = FlowGetNew(tv, dtv, p);
if (f == NULL) {
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return NULL;
}
fb->tail = f;
/* flow is locked */
f->hprev = pf;
/* initialize and return */
FlowInit(f, p);
f->flow_hash = hash;
f->fb = fb;
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Row unlocking */
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return f;
}
if (FlowCompare(f, p) != 0) {
/* we found our flow, lets put it on top of the
* hash list -- this rewards active flows */
/* Find, insert the list into the list head operation, suggesting that the node is likely to be active in a short time, will be frequently searched, used to improve efficiency. */
if (f->hnext) {
f->hnext->hprev = f->hprev;
}
if (f->hprev) {
f->hprev->hnext = f->hnext;
}
if (f == fb->tail) {
fb->tail = f->hprev;
}
f->hnext = fb->head;
f->hprev = NULL;
fb->head->hprev = f;
fb->head = f;
/* found our flow, lock & return */
/* Node Locking */
FLOWLOCK_WRLOCK(f);
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Row unlocking */
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return f;
}
}
}
/* lock & return */
/* Node Locking */
FLOWLOCK_WRLOCK(f);
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Row unlocking */
FBLOCK_UNLOCK(fb);
FlowHashCountUpdate;
return f;
}
Finding interfaces is simpler than finding and inserting interfaces (that is, the functions above), as follows:
Flow *FlowLookupFlowFromHash(const Packet *p)
{
Flow *f = NULL;
/* get the key to our bucket */
uint32_t hash = FlowGetHash(p); /* Hash value of connection*/
/* get our hash bucket and lock it */
FlowBucket *fb = &flow_hash[hash % flow_config.hash_size];/* Locate the corresponding row according to the hash value of the connection*/
/* Row lock */
FBLOCK_LOCK(fb);
SCLogDebug("fb %p fb->head %p", fb, fb->head);
/* see if the bucket already has a flow */
if (fb->head == NULL) {
/* Not found, row unlocked */
FBLOCK_UNLOCK(fb);
return NULL;
}
/* ok, we have a flow in the bucket. Let's find out if it is our flow */
/* If the row has elements, traverse the list to find the corresponding flow*/
f = fb->head;
/* see if this is the flow we are looking for */
/* Whether the first element of the line is the flow to look for, 0 means no, 1 means yes*/
if (FlowCompare(f, p) == 0) {
while (f) {
FlowHashCountIncr;
f = f->hnext;
if (f == NULL) {
/* Row unlocking */
FBLOCK_UNLOCK(fb);
return NULL;
}
if (FlowCompare(f, p) != 0) {
/* we found our flow, lets put it on top of the
* hash list -- this rewards active flows */
/* Find, insert the list into the list head operation, suggesting that the node is likely to be active in a short time, will be frequently searched, used to improve efficiency. */
if (f->hnext) {
f->hnext->hprev = f->hprev;
}
if (f->hprev) {
f->hprev->hnext = f->hnext;
}
if (f == fb->tail) {
fb->tail = f->hprev;
}
f->hnext = fb->head;
f->hprev = NULL;
fb->head->hprev = f;
fb->head = f;
/* found our flow, lock & return */
/* Node Locking */
FLOWLOCK_WRLOCK(f);
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Row unlocking */
FBLOCK_UNLOCK(fb);
return f;
}
}
}
/* lock & return */
/* Node Locking */
FLOWLOCK_WRLOCK(f);
/* update the last seen timestamp of this flow */
COPY_TIMESTAMP(&p->ts,&f->lastts);
/* Find, line unlock */
FBLOCK_UNLOCK(fb);
return f;
}This is my opinion on the use of line locks in suricata. Please criticize and correct it.