--- a/include/waaad/session-api.h	Wed Jul 16 18:33:09 2008 +0900
+++ b/include/waaad/session-api.h	Thu Jul 17 18:17:36 2008 +0900
@@ -144,6 +144,7 @@
  *  sid	  	: pointer to a string containing a session-id.
  *  len		: length of the sid string (which does not need to be '\0'-terminated)
  *  session	: On success, pointer to the session object corresponding.
+ *  new		: if not NULL, set to 1 on return if the session object has been created, 0 otherwise.
  *
  * DESCRIPTION: 
  *   Retrieve a session object from a session-id string. Calling this function makes an implicit call to the
@@ -155,7 +156,7 @@
  *  EINVAL 	: A parameter is invalid.
  *  ENOMEM	: Not enough memory to complete the operation
  */
-int sess_fromsid ( char * sid, size_t len, sess_id_t ** session);
+int sess_fromsid ( char * sid, size_t len, sess_id_t ** session, int * new);
 
 /*
  * FUNCTION:	sess_getsid
@@ -168,6 +169,7 @@
  *   Retrieve the session identifier corresponding to a session object.
  *  The returned sid is a string terminated by \0, suitable for calls to strlen and strcpy.
  *  It may be used for example to set the value of an AVP.
+ *  Note that the sid string is not copied, just its reference... do not free it!
  *
  * RETURN VALUE:
  *  0      	: The sid parameter has been updated.
@@ -254,6 +256,7 @@
  * RETURN VALUE:
  *  0      	: The data has been registered.
  *  EINVAL 	: A parameter is invalid.
+ *  EALREADY	: Data was already associated with this session and client.
  *  ENOMEM	: Not enough memory to complete the operation
  */
 int sess_data_reg ( sess_id_t * session, sess_reg_t * client, void * data, void (*cleanup)(void *) ); 
@@ -308,7 +311,7 @@
 	
 	/* the remaining is session-specific */
 	int (*sess_new)        ( sess_id_t ** session, sess_flags_t flags, char * opt );
-	int (*sess_fromsid)    ( char * sid, size_t len, sess_id_t ** session);
+	int (*sess_fromsid)    ( char * sid, size_t len, sess_id_t ** session, int * new);
 	int (*sess_getsid)     ( sess_id_t * session, char ** sid );
 	int (*sess_link)       ( sess_id_t * session );
 	int (*sess_unlink)     ( sess_id_t ** session );

--- a/waaad/session.c	Wed Jul 16 18:33:09 2008 +0900
+++ b/waaad/session.c	Thu Jul 17 18:17:36 2008 +0900
@@ -38,40 +38,471 @@
  * See session.h and session-api.h for more information on the functions and types involved.
  */
 
+#include <pthread.h>
 #include <errno.h>
+#include <assert.h>
+#include <time.h>
+#include <string.h>
+#include <stdio.h>
 
 #include "waaad-internal.h"
 
+/* More details about the session implementation:
+ *
+ *  The sess_id_t, representing a session id, are stored as _sess_id_t objects in a hash table.
+ * These objects contains generic information about the session: sid string, creation time, ...
+ * They keep a refcount. when the refcount becomes 0, the object is freed.
+ *
+ *  The sess_reg_t represent clients for the module.
+ * The data is stored in a list which root is this _sess_reg_t object.
+ * Each element of the list contains a pointer to a _sess_id_t, a pointer to user's data, and
+ * a reference to a cleanup handler.
+ */
+
+/* Types and globals definitions */
+
+/* The following two integers are used to generate values which are eternaly unique */
+static uint32_t   g_sid_h;	/* initialized to the current time at module initialization */
+static uint32_t   g_sid_l;	/* incremented each time a session id is created. There is no lock yet... hum :s */
+
+/************ sess_id_t ***********/
+
+/* Size of the hash table to hold the sess_id_t objects (pow of 2. ex: 6 => 2^6 = 64). must be between 0 and 31. */
+#define SESS_HASH_SIZE	6
+
+/* How objects are chained. Each sub-list of the hash table is sorted by hash value then strcmp'd. */
+typedef struct _sli_ {
+	struct _sli_  * next;
+	struct _sli_  * prev;
+} _sli_t;
+
+#define _SLI( _sli_ ) ((_sli_t *)(_sli_))
+
+#define SLI_init( _sli ) {		\
+	_SLI(_sli)->next = _SLI(_sli);	\
+	_SLI(_sli)->prev = _SLI(_sli);	\
+}
+
+#define SLI_isempty( _sli ) ( _SLI(_sli)->next == _SLI(_sli) )
+
+#define SLI_remove( _sli ) {				\
+	_SLI(_sli)->next->prev = _SLI(_sli)->prev;	\
+	_SLI(_sli)->prev->next = _SLI(_sli)->next;	\
+	_SLI(_sli)->next = _SLI(_sli);			\
+	_SLI(_sli)->prev = _SLI(_sli);			\
+}
+
+#define SLI_addafter( _ref, _sli ) {		\
+	assert(SLI_isempty( _sli ));		\
+	_SLI(_sli)->next = _SLI(_ref)->next;	\
+	_SLI(_sli)->prev = _SLI(_ref);		\
+	_SLI(_ref)->next->prev = _SLI(_sli);	\
+	_SLI(_ref)->next = _SLI(_sli);		\
+}
+	
+	
+/* The sess_id_t internal definition */
+typedef struct {
+	_sli_t	 	 chain;	/* Chaining information */
+	uint32_t	 hash;	/* The value of the hash of the sid string */
+	int		 eyec;	/* An eye catcher to ensure the object is valid */
+	char 		*sid;	/* The session id string, \0 terminated. */
+	int		 rc;	/* The refcount */
+	struct timespec	 ts;	/* Time of the object creation */
+} _sess_id_t;
+
+/* The eyec value */
+#define _SI_EYEC 0x53551D
+
+/* some useful cast macros */
+#define _SI( _si ) ((_sess_id_t *)(_si))
+
+/* Macro to check an element is valid */
+#define VALIDATE_SI( _si ) ( ((_si) != NULL) && ( _SI(_si)->eyec == _SI_EYEC) )
+
+/* The hash table */
+static struct {
+	_sli_t		sentinel;	/* sentinel element for this sublist */
+	pthread_mutex_t lock;		/* the mutex for this sublist */
+} sess_hash [ 1 << SESS_HASH_SIZE ] ;
+#define H_MASK( __hash ) ((__hash) & (( 1 << SESS_HASH_SIZE ) - 1))
+#define H_LIST( _hash ) (&(sess_hash[H_MASK(_hash)].sentinel))
+#define H_LOCK( _hash ) (&(sess_hash[H_MASK(_hash)].lock    ))
+
+
+/************ sess_reg_t and data ***********/
+
+/* A list element */
+typedef struct {
+	_sli_t		  list;		 /* Elements are ordered in the same order as the hash table: by hash and string */
+	_sess_id_t	 *si;		 /* pointer to the session element this list element refers */
+	void 		(*clncb)(void *);/* The cleanup callback to call on data when the element is destroyed */
+	void		 *data;		 /* The data that is registered for this client and session */
+} _sd_data_t;
+
+#define _SD( _sd_ ) ( (_sd_data_t *)( _sd_) )
+
+/* Now the sess_reg_t internal definition */
+typedef struct {
+	_sli_t		list;	 /* List of the registered clients with no particular order; only to ensure proper cleanup in the end. */
+	int		eyec;	 /* An eye catcher to ensure the object is valid */
+	pthread_mutex_t lock;	 /* A lock to protect the list of data */
+	_sli_t		sentinel;/* Sentinel for the list of _sd_data_t of this client */
+} _sess_reg_t;
+
+/* The sentinel for the list of registered handlers */
+static _sli_t _srt_sentinel;
+static pthread_mutex_t _str_lock; /* lock to protect the list of registered clients */
+
+/* The eyec value */
+#define _SR_EYEC 0x5355DA1A
+
+/* useful cast macro */
+#define _SR( _sr ) ((_sess_reg_t *)(_sr))
+
+/* Macro to check an element is valid */
+#define VALIDATE_SR( _sr ) ( ((_sr) != NULL) && ( _SR(_sr)->eyec == _SR_EYEC) )
+
+	
+/********************************************************************************************************/
+/* Hash function -- credits to Austin Appleby, thank you ^^ */
+/* See http://murmurhash.googlepages.com for more information on this function */
+
+/* Our sid is always aligned properly, so we use the simple MurmurHash2 function */
+#define _HASH_MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
+static uint32_t _hash ( char * sid, size_t len )
+{
+	uint32_t hash = len;
+	char * data = sid;
+	
+	const unsigned int m = 0x5bd1e995;
+	const int r = 24;
+	
+	/* Check the alignment is really correct -- otherwise we have to switch to the other version */
+	assert(((long)sid & 3) == 0);
+
+	while(len >= 4)
+	{
+		/* Mix 4 bytes at a time into the hash */
+		uint32_t k = *(uint32_t *)data;	/* We don't care about the byte order */
+		
+		_HASH_MIX(hash, k, m);
+
+		data += 4;
+		len -= 4;
+	}
+	
+	/* Handle the last few bytes of the input */
+	switch(len) {
+		case 3: hash ^= data[2] << 16;
+		case 2: hash ^= data[1] << 8;
+		case 1: hash ^= data[0];
+	        	hash *= m;
+	}
+
+	/* Do a few final mixes of the hash to ensure the last few
+	   bytes are well-incorporated. */
+	hash ^= hash >> 13;
+	hash *= m;
+	hash ^= hash >> 15;
+
+	return hash;
+} 
+/********************************************************************************************************/
+
+/* Function to compare a (hash, sid) with a sess_id_element. */
+static __inline__ int cmp_si(uint32_t hash1, char * sid1, size_t sid1len,  _sess_id_t * si2)
+{
+	if (hash1 < si2->hash)
+		return -1;
+	if (hash1 > si2->hash)
+		return 1;
+	return strncmp(sid1, si2->sid, sid1len); /* si2->sid is NULL terminated */
+}
+
+/* Function to find a location for a (hash, sid) in a _sess_id_t list.
+ * return 0 if the element is found, -1 if the previous element has been returned (in *loc)
+ * The sublist lock must be held */
+static __inline__ int find_si(uint32_t hash, char * sid, size_t sidlen, _sli_t * sentinel, _sli_t ** loc )
+{
+	int cmp = -1;
+	for ((*loc) = sentinel; (*loc)->next != sentinel; (*loc) = (*loc)->next) {
+		cmp = cmp_si(hash, sid, sidlen, _SI((*loc)->next));
+		if (!cmp)
+			(*loc) = (*loc)->next; /* we found the sid in the list */
+		if (cmp <= 0)	/* The next element in the list is bigger than our element, so stop here */
+			break;
+	}
+	return cmp;
+}
+	
+/* Function to find a location for a _sess_id_t in a _sd_data_t list.
+ * return 0 if the element is found, -1 if the previous element has been returned (in *loc)
+ * The list lock must be held */
+static __inline__ int find_sd(_sess_id_t * sid, _sli_t * sentinel, _sli_t ** loc )
+{
+	int cmp = -1;
+	size_t len = strlen(sid->sid);
+	for ((*loc) = sentinel; (*loc)->next != sentinel; (*loc) = (*loc)->next) {
+		cmp = cmp_si(sid->hash, sid->sid, len, _SD((*loc)->next)->si);
+		if (!cmp)
+			(*loc) = (*loc)->next; /* we found the sid in the list */
+		if (cmp <= 0)	/* The next element in the list is bigger than our element, so stop here */
+			break;
+	}
+	return cmp;
+}
+	
+	
+
+/********************************************************************************************************/
+
 /* Initialize the module */
 int sess_init ( void )
 {
+	int i;
+	
 	TRACE_ENTRY( "" );
-	TRACE_DEBUG (INFO, "@@@ Not implemented yet." );
+	
+	/* Initialize the hash table */
+	for (i = 0; i < sizeof(sess_hash) / sizeof(sess_hash[0]); i++) {
+		int ret = pthread_mutex_init(&sess_hash[i].lock, NULL);
+		if (ret != 0) {
+			TRACE_DEBUG(INFO, "pthread_mutex_init failed: %s", strerror(ret));
+			return ret;
+		}
+		SLI_init( &sess_hash[i].sentinel );
+	}
+	
+	/* Initialize the sentinel for registered clients */
+	SLI_init( &_srt_sentinel );
+	/* and its lock */
+	i = pthread_mutex_init(&_str_lock, NULL);
+	if (i != 0) {
+		TRACE_DEBUG(INFO, "pthread_mutex_init failed: %s", strerror(i));
+		return i;
+	}
+	
+	/* Initialize the global counters */
+	g_sid_h = (uint32_t) time(NULL);
+	g_sid_l = 0;
+	
 	return 0;
 }
 
-/* End of the module */
-int sess_fini ( void )
+/* Find a session object corresponding to a given session-id / or create it */
+int sess_fromsid ( char * sid, size_t len, sess_id_t ** session, int * new )
 {
-	TRACE_ENTRY( "" );
-	TRACE_DEBUG (INFO, "@@@ Not implemented yet." );
-	return 0;
+	int      ret = 0;
+	_sli_t	*li  = NULL;
+	uint32_t hash;
+	
+	TRACE_ENTRY( "%p %d %p", sid, len, session );
+	
+	/* Validate the parameters */
+	if ( (sid == NULL) || (len == 0) || (session == NULL) ) {
+		TRACE_DEBUG(INFO, "Invalid parameters");
+		return EINVAL;
+	}
+	
+	/* Compute the hash value of this string */
+	hash = _hash(sid, len);
+	
+	/* Lock the hash table line */
+	ret = pthread_mutex_lock( H_LOCK(hash) );
+	if (ret != 0) {
+		TRACE_DEBUG(INFO, "pthread_mutex_lock failed: %s", strerror(ret));
+		return ret;
+	}
+	
+	/* Search in the table */
+	ret = find_si( hash, sid, len, H_LIST(hash), &li);
+	if (ret == 0) {
+		/* The element is found in the table */
+		if (new)
+			*new = 0;
+		
+		/* increment its refcount, as if sess_link had been called */
+		_SI(li)->rc++;
+		
+		/* Save the value that must be returned */
+		*session = (sess_id_t *)li; 
+	} else {
+		_sess_id_t * newsi;
+		
+		/* The element did not exist already, li points to the previous element */
+		if (new)
+			*new = 0;
+		
+		/* Create a new element -- how to do this outside the mutex section, and efficiently? */
+		newsi = malloc(sizeof(_sess_id_t));
+		if (newsi == NULL) {
+			log_error("Memory allocation failed: %s\n", strerror(errno));
+			TRACE_DEBUG(INFO, "malloc failed");
+			ret = ENOMEM;
+			goto end;
+		}
+		
+		/* Initialize the element content */
+		memset(newsi, 0, sizeof(_sess_id_t));
+		SLI_init( &newsi->chain );
+		newsi->hash = hash;
+		newsi->eyec = _SI_EYEC;
+		newsi->sid  = malloc(len + 1);
+		if (newsi->sid == NULL) {
+			log_error("Memory allocation failed: %s\n", strerror(errno));
+			TRACE_DEBUG(INFO, "malloc failed");
+			ret = ENOMEM;
+			free(newsi);
+			goto end;
+		}
+		memcpy(newsi->sid, sid, len);
+		newsi->sid[len] = '\0';
+		newsi->rc = 1;
+		ret = clock_gettime(CLOCK_REALTIME, &newsi->ts);
+		if (ret != 0) {
+			TRACE_DEBUG(INFO, "clock_gettime failed: %s", strerror(ret));
+			free(newsi->sid);
+			free(newsi);
+			goto end;
+		}
+			
+		/* Store this element in the list */
+		SLI_addafter(li, newsi);
+		
+		/* Save the reference to it */
+		*session = (sess_id_t *)newsi; 
+	}
+end:	
+	/* Finish, unlock the line */
+	{
+		int __ret = pthread_mutex_unlock( H_LOCK(hash) );
+		if (__ret != 0) {
+			TRACE_DEBUG(INFO, "pthread_mutex_unlock failed: %s", strerror(__ret));
+			return __ret;
+		}
+	}
+	
+	return ret;
 }
 
 /* Create a new session (identifier and object). */
 int sess_new ( sess_id_t ** session, sess_flags_t flags, char * opt )
 {
+	int ret = 0;
+	int new = 0;
+	char * str = NULL;
+	size_t strsz = 0;
+	int mustfree = 0;
+	
 	TRACE_ENTRY( "%p %d %p", session, flags, opt );
-	TRACE_DEBUG (INFO, "@@@ %s: not implemented yet.", __FUNCTION__ );
-	return ENOTSUP;
-}
+	
+	/* Check the parameters */
+	if (session == NULL) {
+		TRACE_DEBUG(INFO, "Invalid parameter");
+		return EINVAL;
+	}
+	
+	/* Ok, first create the identifier following the flags */
+	switch (flags) {
+		case SESSION_NEW_DEFAULT: 	/* "<diameterId>;<high32>;<low32>[;opt]" */
+			{
+				int len;
+				
+				/* Compute the size of the new string */
+				len = strlen(g_pconf->diameter_identity);	/* This could be cached to avoid recomputing it each time */
+				len += 2 * ( 1 /* ';' */ + 10 /* uint32_t max = 4294967295 = 10 digits */ );
+				if (opt)
+					len += strlen(opt);
+				
+				/* Allocate the space for the buffer */
+				str = malloc(len + 1); /* +1 for the final '\0' in the worst case */
+				if (!str) {
+					log_error("Memory allocation failed: %s\n", strerror(errno));
+					TRACE_DEBUG(INFO, "malloc failed");
+					return ENOMEM;
+				}
+				mustfree = 1;
+				memset(str, 0, len+1);
+				
+				/* Increment the value of the low32 */
+				++g_sid_l;
+				
+				/* Now write the new value */
+				if (opt)
+					strsz = snprintf(str, len + 1, "%s;%ju;%ju;%s", g_pconf->diameter_identity, g_sid_h, g_sid_l, opt);
+				else
+					strsz = snprintf(str, len + 1, "%s;%ju;%ju", g_pconf->diameter_identity, g_sid_h, g_sid_l);
+			}
+			
+			break;
+			
+		case SESSION_NEW_SEQUENCE: 	/* "<diameterId>;opt" */
+			if (opt == NULL) {
+				TRACE_DEBUG(INFO, "Invalid parameter");
+				return EINVAL;
+			}
+			{
+				int len;
+				
+				/* Compute the size of the new string */
+				len = strlen(g_pconf->diameter_identity) + 1 + strlen(opt) + 1; /* +1 for the ';' and the final '\0' */
+				
+				/* Allocate the space for the buffer */
+				str = malloc(len);
+				if (!str) {
+					log_error("Memory allocation failed: %s\n", strerror(errno));
+					TRACE_DEBUG(INFO, "malloc failed");
+					return ENOMEM;
+				}
+				mustfree = 1;
+				memset(str, 0, len);
+				
+				strsz = snprintf(str, len, "%s;%s", g_pconf->diameter_identity, opt);
+			}
+			break;
+			
+		case SESSION_NEW_FULL:		/* "opt"  */
+			if (opt == NULL) {
+				TRACE_DEBUG(INFO, "Invalid parameter");
+				return EINVAL;
+			}
+			str = opt;
+			strsz = strlen(str);
+			break;
 
-/* Find a session object corresponding to a given session-id */
-int sess_fromsid ( char * sid, size_t len, sess_id_t ** session)
-{
-	TRACE_ENTRY( "%p %d %p", sid, len, session );
-	TRACE_DEBUG (INFO, "@@@ %s: not implemented yet.", __FUNCTION__ );
-	return ENOTSUP;
+		default:
+			TRACE_DEBUG(INFO, "Invalid parameter");
+			return EINVAL;
+	}
+	
+	/* Now str points to the new session string. Create the new session */
+	
+	ret = sess_fromsid( str, strsz, session, &new );
+	if (ret != 0) {
+		TRACE_DEBUG(INFO, "sess_fromsid failed: %s", strerror(ret));
+		goto end;
+	}
+	
+	/* Check that the object did not already exist before */
+	if (new == 0) {
+		TRACE_DEBUG(INFO, "The session created already existed => The opt parameter must have been bad");
+		
+		/* The string we received was not really a new unique value */
+		ret = sess_unlink(session);
+		if (ret != 0) {
+			TRACE_DEBUG(INFO, "sess_unlink failed: %s", strerror(ret));
+			goto end;
+		}
+		
+		ret = EINVAL;
+	}
+	
+end:
+	if (mustfree)
+		free(str);
+	
+	return ret;
 }
 
 /* Get the session-id string of a session */
@@ -138,3 +569,11 @@
 	return ENOTSUP;
 }
 
+/* End of the module */
+int sess_fini ( void )
+{
+	TRACE_ENTRY( "" );
+	TRACE_DEBUG (INFO, "@@@ Not implemented yet." );
+	return 0;
+}
+