[tor-commits] [obfsproxy/master] Tweak doubly linked list code

14 Jul 2011

commit 65aa57320522002fd4594636c4fdea7e7d3b58ce
Author: Nick Mathewson nickm@torproject.org
Date:   Thu Jul 14 11:35:40 2011 -0400
Tweak doubly linked list code
It's not nice to have to do a linear search of the linked list every
    time we close a connection.  Thus, let's stick the dll_node_t inside
    the structure.  This also simplifies some of the code too.
Also, rename "cl" and "ll" to something real.
---
 src/main.c    |   42 +---------------------------------
 src/network.c |   69 ++++++++++++++++++++++++++++++++++----------------------
 src/network.h |    5 ++-
 src/util.c    |   52 ++++++++++---------------------------------
 src/util.h    |   15 ++++++++++--
 5 files changed, 70 insertions(+), 113 deletions(-)

diff --git a/src/main.c b/src/main.c
index 621a3c9..b43e1e9 100644
--- a/src/main.c
+++ b/src/main.c
@@ -35,9 +35,6 @@ extern int n_supported_protocols;
static struct event_base *the_event_base=NULL;
-/** Doubly linked list holding all our listeners. */
-static dll_t *ll=NULL;
-
 /**
    Prints the obfsproxy usage instructions then exits.
 */
@@ -61,32 +58,6 @@ usage(void)
 }
/**
-   Frees all active listeners.
-*/
-static void
-free_all_listeners(void)
-{
-  static int called_already=0;
-
-  if (called_already)
-    return;
-  if (!ll)
-    return;
-
-  log_info("Closing all listeners.");
-
-  /* Iterate listener doubly linked list and free them all. */ 
-  dll_node_t *ll_node = ll->head;
-  while (ll_node) {
-    listener_free(ll_node->data);
-    dll_remove(ll, ll_node);
-    ll_node = ll->head;
-  }
-
-  called_already++;
-}
-
-/**
    This is called when we receive a signal.
    It figures out the signal type and acts accordingly.
@@ -402,18 +373,9 @@ main(int argc, const char **argv)
if (!temp_listener)
       continue;
-    
+
     log_info("Succesfully created listener %d.", h+1);
-    /* If we don't have a listener dll, create one now. */
-    if (!ll) {
-      ll = calloc(1, sizeof(dll_t));
-      if (!ll)
-        return 1;
-    }
-        
-    /* Append our new listener in the listener dll. */
-    dll_append(ll, temp_listener);
     n_listeners++;
   }
@@ -432,8 +394,6 @@ main(int argc, const char **argv)
     printf("Failed closing logfile!\n");
free_all_listeners(); /* free all listeners in our listener dll */
-  if (ll) /* free listener dll */
-    free(ll);
free(protocol_options);
   free(n_options_array);
diff --git a/src/network.c b/src/network.c
index b29e9dd..605e13d 100644
--- a/src/network.c
+++ b/src/network.c
@@ -21,13 +21,17 @@
 #include <WS2tcpip.h>
 #endif
+/** Doubly linked list holding all our listeners. */
+static dll_t listener_list = DLL_INIT();
+
 struct listener_t {
+  dll_node_t dll_node;
   struct evconnlistener *listener;
   protocol_params_t *proto_params;
 };
/** Doubly linked list holding all connections. */
-static dll_t *cl=NULL;
+static dll_t conn_list = DLL_INIT();
 /** Active connection counter */
 static int n_connections=0;
@@ -67,8 +71,6 @@ start_shutdown(int barbaric)
     shutting_down=1;
if (!n_connections) {
-    if (cl)
-      free(cl);
     finish_shutdown();
     return;
   }
@@ -87,17 +89,13 @@ static void
 close_all_connections(void)
 {
   /** Traverse the dll and close all connections */
-  dll_node_t *cl_node = cl->head;
-  while (cl_node) {
-    conn_free(cl_node->data);
-
-    if (cl) { /* last conn_free() wipes the cl. */
-      cl_node = cl->head; /* move to next connection */
-    } else {
-      assert(!n_connections);
-      return; /* connections are now all closed. */  
-    }
-  }    
+  while (conn_list.head) {
+    conn_t *conn = UPCAST(conn_t, dll_node, conn_list.head);
+    conn_free(conn); /* removes it */
+
+    return; /* connections are now all closed. */
+  }
+  assert(!n_connections);
 }
/**
@@ -121,14 +119,8 @@ listener_new(struct event_base *base,
   }
/** If we don't have a connection dll, create one now. */
-  if (!cl) {
-    cl = calloc(1, sizeof(dll_t));
-    if (!cl)
-      return NULL;
-  }
-
   lsn->proto_params = proto_params;
-  
+
   lsn->listener = evconnlistener_new_bind(base, simple_listener_cb, lsn,
                                           flags,
                                           -1,
@@ -141,6 +133,8 @@ listener_new(struct event_base *base,
     return NULL;
   }
+  dll_append(&listener_list, &lsn->dll_node);
+
   return lsn;
 }
@@ -151,10 +145,35 @@ listener_free(listener_t *lsn)
     evconnlistener_free(lsn->listener);
   if (lsn->proto_params)
     proto_params_free(lsn->proto_params);
+
+  dll_remove(&listener_list, &lsn->dll_node);
+
   memset(lsn, 0xb0, sizeof(listener_t));
   free(lsn);
 }
+/**
+   Frees all active listeners.
+*/
+void
+free_all_listeners(void)
+{
+  static int called_already=0;
+
+  if (called_already)
+    return;
+
+  log_info("Closing all listeners.");
+
+  /* Iterate listener doubly linked list and free them all. */
+  while (listener_list.head) {
+    listener_t *listener = UPCAST(listener_t, dll_node, listener_list.head);
+    listener_free(listener);
+  }
+
+  called_already++;
+}
+
 static void
 simple_listener_cb(struct evconnlistener *evcl,
     evutil_socket_t fd, struct sockaddr *sourceaddr, int socklen, void *arg)
@@ -239,7 +258,7 @@ simple_listener_cb(struct evconnlistener *evcl,
   }
/* add conn to the linked list of connections */
-  if (dll_append(cl, conn)<0)
+  if (dll_append(&conn_list, &conn->dll_node)<0)
     goto err;
   n_connections++;
@@ -267,7 +286,7 @@ conn_free(conn_t *conn)
     bufferevent_free(conn->output);
/* remove conn from the linked list of connections */
-  dll_remove_with_data(cl, conn);
+  dll_remove(&conn_list, &conn->dll_node);
   n_connections--;
memset(conn, 0x99, sizeof(conn_t));
@@ -280,10 +299,6 @@ conn_free(conn_t *conn)
   /** If this was the last connection AND we are shutting down,
       finish shutdown. */
   if (!n_connections && shutting_down) {
-    if (cl) { /* free connection dll */ 
-      free(cl);
-      cl = NULL;
-    }
     finish_shutdown();
   }
 }
diff --git a/src/network.h b/src/network.h
index 28a0d7d..dc6b583 100644
--- a/src/network.h
+++ b/src/network.h
@@ -12,8 +12,7 @@
 #include <event2/listener.h>
 #include <event2/event.h>
-
-typedef struct listener_t *listener;
+#include "util.h"
struct sockaddr;
 struct event_base;
@@ -46,11 +45,13 @@ struct addrinfo;
 listener_t *listener_new(struct event_base *base,
                          struct protocol_params_t *params);
 void listener_free(listener_t *listener);
+void free_all_listeners(void);
void start_shutdown(int barbaric);
#ifdef NETWORK_PRIVATE
 typedef struct conn_t {
+  dll_node_t dll_node;
   struct socks_state_t *socks_state;
   struct protocol_t *proto; /* ASN Do we like this here? We probably don't.
                                But it's so convenient!! So convenient! */
diff --git a/src/util.c b/src/util.c
index 1ee7bcb..06e89b9 100644
--- a/src/util.c
+++ b/src/util.c
@@ -152,7 +152,7 @@ obfs_vsnprintf(char *str, size_t size, const char *format, va_list args)
/**
    Insert 'new_node' after 'node' in the doubly linked list 'list'.
-*/ 
+*/
 static void
 dll_insert_after(dll_t *list, dll_node_t *node, dll_node_t *new_node)
 {
@@ -191,6 +191,13 @@ dll_insert_before(dll_t *list, dll_node_t *node, dll_node_t *new_node)
     node->prev->next = new_node;
   node->prev = new_node;
 }
+
+/** Initialize <b>list</b> as an empty list. */
+void
+dll_init(dll_t *list)
+{
+  list->head = list->tail = NULL;
+}
/**
    Insert 'node' in the beginning of the doubly linked 'list'.
@@ -218,25 +225,16 @@ dll_insert_beginning(dll_t *list, dll_node_t *node)
     Returns 1 on success, -1 on fail.
 */
 int
-dll_append(dll_t *list, void *data)
+dll_append(dll_t *list, dll_node_t *node)
 {
-  assert(data);
-
-  if (!list)
-    return -1;
+  assert(list);
+  assert(node);
-  dll_node_t *node;
-  
-  node = calloc(1, sizeof(dll_node_t));
-  if (!node)
-    return -1;
-  node->data = data;
-  
   if (!list->tail)
     dll_insert_beginning(list, node);
   else
     dll_insert_after(list, list->tail, node);
-      
+
   return 1;
 }
@@ -260,32 +258,6 @@ dll_remove(dll_t *list, dll_node_t *node)
     list->tail = node->prev;
   else
     node->next->prev = node->prev;
-
-  free(node);
-}
-
-/**
-   Removes node carrying 'data' from the doubly linked list 'list'.
-   It frees the list node, but leaves 'data' intact.
-*/
-void
-dll_remove_with_data(dll_t *list, void *data)
-{
-  assert(data);
-  
-  if (!list)
-    return;
-
-  dll_node_t *node = list->head;
-  while (node) {
-    if (node->data == data) {
-      dll_remove(list, node);
-      return;
-    } else {
-      node = node->next;
-    }
-  }
-  assert(0); /*too brutal?*/
 }
/************************ Logging Subsystem *************************/
diff --git a/src/util.h b/src/util.h
index 999c5df..7e73cee 100644
--- a/src/util.h
+++ b/src/util.h
@@ -52,11 +52,19 @@ int obfs_snprintf(char *str, size_t size,
/***** Doubly Linked List stuff. *****/
+#define OFFSETOF(container_type, element) \
+  (((char*)&((container_type*)0)->element) - ((char*) ((container_type*)0)))
+
+#define UPCAST(container_type, element, ptr) \
+  (container_type*) (                                                   \
+         ((char*)ptr) - OFFSETOF(container_type, element)   \
+                    )
+
+
 /** A doubly linked list node.
     [algorithms ripped off Wikipedia (Doubly_linked_list) ] */
 typedef struct dll_node_t {
   struct dll_node_t *next, *prev;
-  void *data;
 } dll_node_t;
/** A doubly linked list. */
@@ -65,9 +73,10 @@ typedef struct dll_t {
   struct dll_node_t *tail;
 } dll_t;
-int dll_append(dll_t *list, void *data);
+void dll_init(dll_t *list);
+int dll_append(dll_t *list, dll_node_t *node);
 void dll_remove(dll_t *list, dll_node_t *node);
-void dll_remove_with_data(dll_t *list, void *data);
+#define DLL_INIT() { NULL, NULL }
/***** Logging subsystem stuff. *****/

    

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

[tor-commits] [obfsproxy/master] Tweak doubly linked list code