Merge lp:~zorba-coders/zorba/bug-1042840 into lp:zorba

[Markos Zaharioudakis]

Fixed bug #1042840 (qname pool free-list corruption)

Fixed bug #1042840 (qname pool free-list corruption)

[lp:~zorba-coders/zorba/bug-1042840]

11005. By Markos Zaharioudakis on 2012-08-28

fixed bug #1042840$

[Markos Zaharioudakis (markos-za)]

review: Approve

[Zorba Build Bot (zorba-buildbot)]

Validation queue starting for merge proposal.
Log at: http://zorbatest.lambda.nu:8080/remotequeue/bug-1042840-2012-08-28T19-42-04.317Z/log.html

[Zorba Build Bot (zorba-buildbot)]

Validation queue job bug-1042840-2012-08-28T19-42-04.317Z is finished. The final status was:

All tests succeeded!

=== modified file 'ChangeLog'
--- ChangeLog	2012-08-28 07:15:46 +0000
+++ ChangeLog	2012-08-28 19:26:23 +0000
@@ -13,7 +13,7 @@
   * Fixed bug #1024892 (index declaration references udf declared after the index)
   * Fixed bug #1038410 (Memory leaks in parser, trace iterator, and general index)
   * Fixed bug #1039488 (inserting more than one pair at once in a JSON object)
-
+  * Fixed bug #1042840 (qname pool free-list corruption)
 
 version 2.6
 

=== modified file 'src/store/naive/qname_pool.cpp'
--- src/store/naive/qname_pool.cpp	2012-08-28 07:03:17 +0000
+++ src/store/naive/qname_pool.cpp	2012-08-28 19:26:23 +0000
@@ -48,7 +48,7 @@
   QNameItem* qn = &theCache[1];
   QNameItem* last = qn + size - 1;
 
-  for (uint16_t i = 1; qn < last; qn++, i++)
+  for (csize i = 1; qn < last; qn++, i++)
   {
     qn->theNextFree = i + 1;
     qn->thePrevFree = i - 1;
@@ -82,23 +82,121 @@
 /*******************************************************************************
 
 ********************************************************************************/
+void QNamePool::addInFreeList(QNameItem* qn)
+{
+  assert(qn->thePrevFree == 0);
+  assert(qn->theNextFree == 0);
+  assert(qn->getRefCount() == 0);
+  assert(theCache[theFirstFree].thePrevFree == 0);
+
+  qn->theNextFree = (uint16_t)theFirstFree;
+
+  if (theFirstFree != 0)
+    theCache[theFirstFree].thePrevFree = qn->thePosition;
+
+  theFirstFree = qn->thePosition;
+
+  theNumFree++;
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
+void QNamePool::removeFromFreeList(QNameItem* qn)
+{
+  assert(qn->isInCache());
+
+  if (qn->theNextFree == 0 && qn->thePrevFree == 0)
+  {
+    // Either qn does not belong to the free list, or is the only one in the
+    // free list
+
+    if (theFirstFree != qn->thePosition)
+      return;
+  }
+
+  assert(qn->getRefCount() == 0);
+
+  if (qn->theNextFree != 0)
+  {
+    assert(theCache[qn->theNextFree].thePrevFree = qn->thePosition);
+
+    theCache[qn->theNextFree].thePrevFree = qn->thePrevFree;
+  }
+
+  if (qn->thePrevFree != 0)
+  {
+    assert(theCache[qn->thePrevFree].theNextFree = qn->thePosition);
+    
+    theCache[qn->thePrevFree].theNextFree = qn->theNextFree;
+  }
+  else
+  {
+    assert(theFirstFree == qn->thePosition);
+
+    theFirstFree = qn->theNextFree;
+  }
+
+  qn->theNextFree = qn->thePrevFree = 0;
+
+  theNumFree--;
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
+QNameItem* QNamePool::popFreeList()
+{
+  if (theFirstFree != 0)
+  {
+    assert(theNumFree > 0);
+
+    QNameItem* qn = &theCache[theFirstFree];
+
+    assert(qn->getRefCount() == 0);
+
+    theFirstFree = qn->theNextFree;
+
+    if (theFirstFree != 0)
+    {
+      assert(theCache[theFirstFree].thePrevFree == qn->thePosition);
+      theCache[theFirstFree].thePrevFree = 0;
+    }
+
+    qn->theNextFree = qn->thePrevFree = 0;
+
+    theNumFree--;
+
+    return qn;
+  }
+  else
+  {
+    assert(theNumFree == 0);
+    return NULL;
+  }
+}
+
+
+/*******************************************************************************
+
+********************************************************************************/
 void QNamePool::remove(QNameItem* qn)
 {
   QNameItem* normVictim = NULL;
 
   SYNC_CODE(theHashSet.theMutex.lock(); \
-            bool haveLock = true;)
+  bool haveLock = true;)
 
-  try {
+  try 
+  {
     if (qn->getRefCount() > 0)
       return;
 
     if (qn->isInCache())
     {
-      qn->theNextFree = (uint16_t)theFirstFree;
-      theCache[theFirstFree].thePrevFree = qn->thePosition;
-      theFirstFree = qn->thePosition;
-      theNumFree++;
+      addInFreeList(qn);
     }
     else
     {
@@ -114,13 +212,16 @@
     // Releasing the lock here to avoid deadlock, because decrementing the 
     // normVictim counter might reenter QNamePool::remove.
     SYNC_CODE(theHashSet.theMutex.unlock(); \
-              haveLock = false;)
+    haveLock = false;)
+
     if (normVictim)
     {
       normVictim->removeReference();
     }
 
-  } catch(...) {
+  }
+  catch(...)
+  {
     SYNC_CODE(if (haveLock) \
               theHashSet.theMutex.unlock();)
               
@@ -142,8 +243,7 @@
 store::Item_t QNamePool::insert(
     const char* ns,
     const char* pre,
-    const char* ln,
-    bool        sync)
+    const char* ln)
 {
   QNameItem* qn;
   QNameItem* normVictim = NULL;
@@ -168,18 +268,16 @@
     SYNC_CODE(theHashSet.theMutex.lock();\
     haveLock = true;)
 
-    QNHashEntry* entry = hashFind(ns, pre, ln,
-                                  (ulong)pooledNs.size(),
-                                  (ulong)strlen(pre),
-                                  (ulong)strlen(ln),
-                                  hval);
+    QNHashEntry* entry = 
+    hashFind(ns, pre, ln, pooledNs.size(), strlen(pre), strlen(ln), hval);
+
     if (entry == 0)
     {
       if (normalized)
       {
         // Build a new QName (either new object or in cache).
         qn = cacheInsert(normVictim);
-        qn->initializeAsNormalizedQName(pooledNs, zstring(ln));
+        qn->initializeAsNormalizedQName(pooledNs, ln);
       }
       else
       {
@@ -188,7 +286,7 @@
           SYNC_CODE(theHashSet.theMutex.unlock();\
           haveLock = false;)
 
-          normItem = insert(ns, NULL, ln, false);
+          normItem = insert(ns, NULL, ln);
           normQName = static_cast<QNameItem*>(normItem.getp());
           goto retry;
         }
@@ -236,8 +334,7 @@
 store::Item_t QNamePool::insert(
     const zstring& ns,
     const zstring& pre,
-    const zstring& ln,
-    bool sync)
+    const zstring& ln)
 {
   QNameItem* qn = NULL;
   QNameItem* normVictim = NULL;
@@ -259,11 +356,11 @@
     SYNC_CODE(theHashSet.theMutex.lock();\
     haveLock = true;)
 
-    QNHashEntry* entry = hashFind(ns.c_str(), pre.c_str(), ln.c_str(),
-                                  (ulong)ns.size(),
-                                  (ulong)pre.size(), 
-                                  (ulong)ln.size(),
-                                  hval);
+    QNHashEntry* entry =
+    hashFind(ns.c_str(), pre.c_str(), ln.c_str(),
+             ns.size(), pre.size(), ln.size(),
+             hval);
+
     if (entry == 0)
     {
       if (normalized)
@@ -280,7 +377,7 @@
           haveLock = false;)
 
           // This call will need the lock.
-          normItem = insert(pooledNs, zstring(), ln, false);
+          normItem = insert(pooledNs, zstring(), ln);
           normQName = static_cast<QNameItem*>(normItem.getp());
 
           goto retry;
@@ -329,30 +426,23 @@
 ********************************************************************************/
 QNameItem* QNamePool::cacheInsert(QNameItem*& normVictim)
 {
-  assert (normVictim == NULL);
-  if (theFirstFree != 0)
-  {
-    QNameItem* qn = &theCache[theFirstFree];
-
-    theFirstFree = qn->theNextFree;
-    theCache[theFirstFree].thePrevFree = 0;
-
-    if (qn->isValid())
-    {
-      ulong hval = CompareFunction::hash(qn);
-      theHashSet.eraseNoSync(qn, hval);
-      qn->invalidate(true, &normVictim);
-    }
-
-    qn->theNextFree = qn->thePrevFree = 0;
-
-    theNumFree--;
-    return qn;
-  }
-  else
+  assert(normVictim == NULL);
+
+  QNameItem* qn = popFreeList();
+
+  if (qn == NULL)
   {
     return new QNameItem();
   }
+
+  if (qn->isValid())
+  {
+    ulong hval = CompareFunction::hash(qn);
+    theHashSet.eraseNoSync(qn, hval);
+    qn->invalidate(true, &normVictim);
+  }
+  
+  return qn;
 }
 
 
@@ -362,23 +452,9 @@
 ********************************************************************************/
 void QNamePool::cachePin(QNameItem* qn)
 {
-  if (qn->isInCache() && (qn->theNextFree != 0 || qn->thePrevFree != 0))
+  if (qn->isInCache())
   {
-    if (qn->theNextFree != 0)
-      theCache[qn->theNextFree].thePrevFree = qn->thePrevFree;
-
-    if (qn->thePrevFree != 0)
-    {
-      theCache[qn->thePrevFree].theNextFree = qn->theNextFree;
-    }
-    else
-    {
-      assert(theFirstFree == qn->thePosition);
-      theFirstFree = qn->theNextFree;
-    }
-
-    qn->theNextFree = qn->thePrevFree = 0;
-    theNumFree--;
+    removeFromFreeList(qn);
   }
 }
 
@@ -390,10 +466,10 @@
     const char* ns,
     const char* pre,
     const char* ln,
-    ulong       nslen,
-    ulong       prelen,
-    ulong       lnlen,
-    ulong       hval)
+    csize       nslen,
+    csize       prelen,
+    csize       lnlen,
+    csize       hval)
 {
   QNHashEntry* entry = theHashSet.bucket(hval);
 

=== modified file 'src/store/naive/qname_pool.h'
--- src/store/naive/qname_pool.h	2012-08-16 18:31:02 +0000
+++ src/store/naive/qname_pool.h	2012-08-28 19:26:23 +0000
@@ -32,22 +32,31 @@
 
 /*******************************************************************************
 
-  theCache       : An array of QName slots that is managed as a cache. This
-                   means that slots that are not used are placed in a free list.
-                   When a new qname is inserted in the cache, a slot is taken
-                   from the free list and the qname currently in that slot is
-                   replaced with the new slot.
-  theCacheSize   : The size of theCache (number of slots). This size is given
-                   as a param to the QNamePool constructor, and it never changes
-                   afterwards. 
-  theFirstFree   : The position in theCache of the 1st free slot. NOTE: the 1st
-                   slot of theCache (at position 0) is reserved (i.e., never
-                   used) so that position 0 can be used to indicate the end of
-                   the free list.
-  theNumFree     : Number of free slots in theCache.
-
-  theHashSet     : A hash set mapping qnames (i.e. triplets of strings) to
-                   QName slots.
+  theCache :
+  ----------
+  An array of QName slots that is managed as a cache. This means that slots that
+  are not used are placed in a free list. When a new qname is inserted in the
+  cache, a slot is taken from the free list and the qname currently in that slot
+  is replaced with the new slot.
+
+  theCacheSize :
+  --------------
+  The size of theCache (number of slots). This size is given as a param to the
+  QNamePool constructor, and it never changes afterwards.
+ 
+  theFirstFree :
+  --------------
+  The position in theCache of the 1st free slot. NOTE: the 1st slot of theCache
+  (at position 0) is reserved (i.e., never used) so that position 0 can be used
+  to indicate the end of the free list.
+
+  theNumFree :
+  ------------
+  Number of free slots in theCache.
+
+  theHashSet :
+  ------------
+  A hash set mapping qnames (i.e. triplets of strings) to QName slots.
 
 ********************************************************************************/
 class QNamePool
@@ -106,17 +115,9 @@
 
   ~QNamePool();
 
-  store::Item_t insert(
-      const char* ns,
-      const char* pre,
-      const char* ln,
-      bool sync = true);
+  store::Item_t insert(const char* ns, const char* pre, const char* ln);
   
-  store::Item_t insert(
-      const zstring& ns,
-      const zstring& pre,
-      const zstring& ln,
-      bool sync = true);
+  store::Item_t insert(const zstring& ns, const zstring& pre, const zstring& ln);
   
   void remove(QNameItem* qn);
 
@@ -129,10 +130,16 @@
       const char* ns,
       const char* pre,
       const char* ln,
-      ulong       nslen,
-      ulong       prelen,
-      ulong       lnlen,
-      ulong       hval);
+      csize       nslen,
+      csize       prelen,
+      csize       lnlen,
+      csize       hval);
+
+  void addInFreeList(QNameItem* qn);
+
+  void removeFromFreeList(QNameItem* qn);
+
+  QNameItem* popFreeList();
 };