Changeset: 24c408dcf765 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=24c408dcf765
Modified Files:
monetdb5/mal/mal_debugger.c
monetdb5/mal/mal_namespace.c
monetdb5/mal/mal_namespace.h
Branch: Oct2012
Log Message:
Concurrency on namespace
This patch addresses the bug #3163
The concurrency conflict has been addressed in the namespace in Oct branch.
Running on my desktop and a small version of the database (5000),
which is enough the create the load and 100 concurrent users
(of which 64 are accepted) does not crash the server.
However, if you run the script with a naively large sequence (eg. 1000)
you will encounter bash/OS fork/resource limitations.
diffs (truncated from 363 to 300 lines):
diff --git a/monetdb5/mal/mal_debugger.c b/monetdb5/mal/mal_debugger.c
--- a/monetdb5/mal/mal_debugger.c
+++ b/monetdb5/mal/mal_debugger.c
@@ -913,9 +913,6 @@ retryRead:
printStackElm(out, mb, stk->stk + i, i, size,
first);
continue;
}
- case 'S':
- dumpNamespaceStatistics(out, 1);
- break;
case 'u':
if (strncmp("unset", b, 5)) {
skipWord(cntxt, b);
diff --git a/monetdb5/mal/mal_namespace.c b/monetdb5/mal/mal_namespace.c
--- a/monetdb5/mal/mal_namespace.c
+++ b/monetdb5/mal/mal_namespace.c
@@ -18,8 +18,8 @@
*/
/*
- * @a M.L. Kersten
- * @+ Name Space Management.
+ * (co) M.L. Kersten
+ * Name Space Management.
* Significant speed improvement at type resolution and during the
* optimization phases can be gained when each module or function identifier is
* replaced by a fixed length internal identifier. This translation is
@@ -39,118 +39,76 @@
* The space can, however, also become polluted with identifiers generated on
the fly.
* Compilers are adviced to be conservative in their naming, or explicitly
manage
* the name space by deletion of non-used names once in a while.
- */
-/*
- * @+ Code bodies
+ *
+ * Code bodies
* The Namespace block is organized using a simple hashstructure over the first
- * character. Better structures can be introduced when searching becomes
+ * two characters. Better structures can be introduced when searching becomes
* too expensive. An alternative would be to use a BAT to handle the
collection.
*/
#include "monetdb_config.h"
#include "mal_type.h"
#include "mal_namespace.h"
#include "mal_exception.h"
-#define MAXIDENTIFIERS 2048
+#define MAXIDENTIFIERS 4096
+
+#define HASHMASK 4095
+#define NMEHASH(X,L) (L > 1 ?( ((*X) ^ ((*(X+1)) << 7)) & HASHMASK): (*X))
+//#define NMEHASH(X,L) (*X)
typedef struct NAMESPACE{
int size; /* amount of space available */
int nmetop;
str *nme;
int *link;
- int *hit;
size_t *length;
- int totalhit;
} Namespace;
static Namespace namespace;
-#ifdef _BACKUP_
-/* code to aid hunting for illegal frees on the namespace */
-static Namespace backup;
-#endif
-static void expandNamespace(int incr){
+static void expandNamespace(void){
str *nme;
size_t *length;
- int *link, *hit, newsize;
+ int *link, newsize, incr = 2048;
- assert( incr > 0 );
-
- newsize= namespace.size+incr;
+ newsize= namespace.size + incr;
nme= (str *) GDKmalloc(sizeof(str *) * newsize);
assert(nme != NULL); /* we cannot continue */
link= (int *) GDKmalloc(sizeof(int) * newsize);
assert(link != NULL); /* we cannot continue */
- hit = (int *) GDKmalloc(sizeof(int) * newsize);
- assert(hit != NULL); /* we cannot continue */
length = (size_t *) GDKmalloc(sizeof(size_t) * newsize);
assert(length != NULL); /* we cannot continue */
memcpy(nme, namespace.nme, sizeof(str *) * namespace.nmetop);
memcpy(link, namespace.link, sizeof(int) * namespace.nmetop);
- memcpy(hit, namespace.hit, sizeof(int) * namespace.nmetop);
memcpy(length, namespace.length, sizeof(size_t) * namespace.nmetop);
namespace.size += incr;
- namespace.totalhit= 0;
GDKfree(namespace.nme); namespace.nme= nme;
GDKfree(namespace.link); namespace.link= link;
- GDKfree(namespace.hit); namespace.hit= hit;
GDKfree(namespace.length); namespace.length= length;
+}
-#ifdef _BACKUP_
- nme= (str *) GDKmalloc(sizeof(str *) * (backup.nmetop+incr));
- link= (int *) GDKmalloc(sizeof(int) * (backup.nmetop+incr));
- hit = (int *) GDKmalloc(sizeof(int) * (backup.nmetop+incr));
- length = (size)t *) GDKmalloc(sizeof(size_t) * (backup.nmetop+incr));
- memcpy(nme, backup.nme, sizeof(str *) * backup.nmetop);
- memcpy(link, backup.link, sizeof(int) * backup.nmetop);
- memcpy(hit, backup.hit, sizeof(int) * backup.nmetop);
- memcpy(length, backup.hit, sizeof(size_t) * backup.nmetop);
-
- backup.size += incr;
- backup.totalhit= 0;
- GDKfree(backup.nme); backup.nme= nme;
- GDKfree(backup.link); backup.link= link;
- GDKfree(backup.hit); backup.hit= hit;
- GDKfree(backup.length); backup.length= length;
-#endif
-
-}
void initNamespace(void) {
+ assert(namespace.nme == NULL);
+ assert(namespace.link == NULL);
+ assert(namespace.length == NULL);
namespace.nme= (str *) GDKzalloc(sizeof(str *) * MAXIDENTIFIERS);
namespace.link= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
- namespace.hit= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
namespace.length= (size_t *) GDKzalloc(sizeof(size_t) * MAXIDENTIFIERS);
if ( namespace.nme == NULL ||
namespace.link == NULL ||
- namespace.hit == NULL ||
namespace.length == NULL) {
/* absolute an error we can not recover from */
showException(GDKout, MAL,"initNamespace",MAL_MALLOC_FAIL);
mal_exit();
}
namespace.size = MAXIDENTIFIERS;
- namespace.nmetop= 256; /* hash overflow */
-
-#ifdef _BACKUP_
- backup.nme= (str *) GDKzalloc(sizeof(str *) * MAXIDENTIFIERS);
- backup.link= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
- backup.hit= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
- backup.length= (size_t *) GDKzalloc(sizeof(size_t) * MAXIDENTIFIERS);
- if ( backup.nme == NULL ||
- backup.link == NULL ||
- backup.hit == NULL ||
- backup.length == NULL) {
- /* absolute an error we can not recover from */
- showException(GDKout, MAL,"initNamespace",MAL_MALLOC_FAIL);
- mal_exit();
- }
- backup.size = MAXIDENTIFIERS;
- backup.nmetop= 256; /* hash overflow */
-#endif
+ namespace.nmetop= HASHMASK; /* hash overflow */
}
void finishNamespace(void) {
int i;
+
+ MT_lock_set(&mal_contextLock, "putName");
for(i=0;i<namespace.nmetop; i++) {
if( namespace.nme[i])
GDKfree(namespace.nme[i]);
@@ -158,30 +116,11 @@ void finishNamespace(void) {
}
GDKfree(namespace.nme); namespace.nme= 0;
GDKfree(namespace.link); namespace.link= 0;
- GDKfree(namespace.hit); namespace.hit= 0;
GDKfree(namespace.length); namespace.length= 0;
-#ifdef _BACKUP_
- GDKfree(backup.nme); backup.nme=0;
- GDKfree(backup.link); backup.link=0;
- GDKfree(backup.hit); backup.hit=0;
- GDKfree(backup.length); backup.length=0;
-#endif
+ MT_lock_unset(&mal_contextLock, "putName");
}
-#ifdef _BACKUP_
-void chkName(int l){
- int i;
- if( namespace.nme[l] && strcmp(namespace.nme[l],backup.nme[l])!=0){
- printf("error in namespace %d\n",l);
- printf("backup %s\n",backup.nme[l]);
- for( i=0; i< strlen(backup.nme[l]); i++)
- printf("[%d] %d '%c'\n",i, namespace.nme[l][i],
namespace.nme[l][i]);
-
- }
-}
-#endif
/*
- * @-
* Before a name is being stored we should check for its occurrence first.
* The administration is initialized incrementally.
* Beware, the routine getName is not thread safe under updates
@@ -192,21 +131,18 @@ str getName(str nme, size_t len)
size_t l;
if(len == 0 || nme== NULL || *nme==0) return 0;
- for(l= nme[0]; l && namespace.nme[l]; l= namespace.link[l]){
-#ifdef _BACKUP_
- chkName(l);
-#endif
+ MT_lock_set(&mal_contextLock, "putName");
+ for(l= NMEHASH(nme,len); l && namespace.nme[l]; l= namespace.link[l]){
if (namespace.length[l] == len &&
strncmp(nme,namespace.nme[l],len)==0) {
- namespace.hit[l]++;
- namespace.totalhit++;
+ MT_lock_unset(&mal_contextLock, "putName");
return namespace.nme[l];
}
}
+ MT_lock_unset(&mal_contextLock, "putName");
return 0;
}
/*
- * @-
* Name deletion from the namespace is tricky, because there may
* be multiple threads active on the structure. Moreover, the
* symbol may be picked up by a concurrent thread and stored
@@ -220,119 +156,43 @@ void delName(str nme, size_t len){
n= getName(nme,len);
if( nme[0]==0 || n == 0) return ;
+ /*Namespace garbage collection not available yet
MT_lock_set(&mal_contextLock, "putName");
- /*Namespace garbage collection not available yet */
MT_lock_unset(&mal_contextLock, "putName");
+ */
}
str putName(str nme, size_t len)
{
size_t l,top;
char buf[MAXIDENTLEN];
- if( nme == NULL)
+ if( nme == NULL || len == 0)
return NULL;
- for(l= nme[0]; l && namespace.nme[l]; l= namespace.link[l]){
-#ifdef _BACKUP_
- chkName(l);
-#endif
+ /* protect this, as it will be updated by multiple threads */
+ MT_lock_set(&mal_contextLock, "putName");
+ for(l= NMEHASH(nme,len); l && namespace.nme[l]; l= namespace.link[l]){
if( namespace.length[l] == len &&
strncmp(nme,namespace.nme[l],len) == 0 ) {
- namespace.hit[l]++;
- namespace.totalhit++;
- /* aggressive test for reorganization needs */
- /* this is a potential concurreny problem */
-/* Move it to a separate routine, avoid excessive locking and
- serialization
- if( k && 2*namespace.hit[k] < namespace.hit[l]){
- str s;
- int h,i;
- s= namespace.nme[l]; namespace.nme[l]=
namespace.nme[k];
- namespace.nme[k]=s;
- h= namespace.hit[l];
namespace.hit[l]=namespace.hit[k];
- namespace.hit[k]= h;
- i= namespace.length[l];
namespace.length[l]=namespace.length[k];
- namespace.length[k]= i;
-
-#ifdef _BACKUP_
- s= backup.nme[l]; backup.nme[l]= backup.nme[k];
- backup.nme[k]=s;
- i= backup.hit[l]; backup.hit[l]=backup.hit[k];
- backup.hit[k]= i;
- i= backup.length[l];
backup.length[l]=backup.length[k];
- backup.length[k]= i;
-#endif
- l=k;
- }
-*/
+ MT_lock_unset(&mal_contextLock, "putName");
return namespace.nme[l];
}
}
- /* protect this, as it will be updated by multiple threads */
- MT_lock_set(&mal_contextLock, "putName");
if(len>=MAXIDENTLEN)
len = MAXIDENTLEN - 1;
memcpy(buf, nme, len);
buf[len]=0;
if( namespace.nmetop+1== namespace.size)
- expandNamespace(MAXIDENTIFIERS);
- l= nme[0];
+ expandNamespace();
+ l= NMEHASH(nme,len);
top= namespace.nme[l]== 0? (int)l: namespace.nmetop;
namespace.nme[top]= GDKstrdup(buf);
namespace.link[top]= namespace.link[l];
if ((int)top == namespace.nmetop)
namespace.link[l] = (int)top;
- namespace.hit[top]= 0;
namespace.length[top]= len;
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
