2008/7/29 Ingo Weinhold <ingo_weinhold@xxxxxx>: >> Because as I said, the performance issues happens only on process exit and >> from >> an user point of view it shouldn't be a problem. > > Not sure what to say. You wrote yourself in your previous mail that SETVAL > and SETALL are affected (BTW, the latter is even very suboptimally > implemented and thus O(m*n) with m = number of sems in the set and n = total > number of undo entries). And as I wrote in my previous mail RMID should be > affected in the same way. So the performance issues when a lot of semaphores > are used are definitely not limited to program exit only. Exactly. It also affect the performances of initialization, as that's what SETVAL and SETALL are. Theorically during inizialization there won't be any process waiting on it, nor there be a sem_undo request queued. The other design I started with, required a private list in every XsiSemaphore, so that when SETALL or SETVAL was called, all it has to do was iterate through the list and set the sem_undo value to zero. Despite improving the inizialization performance, it would also require to add another list to the team to keep an object per semaphore used with SEM_UNDO. This list would be accessed at exit time in the very same manner the XsiSemaphore private one is. This design though, add the complexity of keeping the two list synchronized, plus something else I don't recall right now (btw: second time I write this email, the first got lost thanks to gmail). Anyway, I decided to choose semplicity as I though that the performances lost on exit and initialization won't be a big problem. Theorically there won't even be a process with requested sem_undo at inizialization, as theorically, SETVAL and SETALL are the very first operation done on a set. >> I'd actually prefer to reuse some other test like the one I've attached in >> the previous email, > > That's fine, if you find enough for a reasonable coverage. It seems like the Linux Testsuite Project contains enough test applications. I'v ported and ran the one attached. I'm also attaching the result of one of these test. I'm planning to port some more. > >> or use some real programs like bonnie++. > > "Real programs" are definitely not a good substitute for unit tests, since > they usually use only a small fraction of the API and possible test cases. > Please understand that others have to work with the implementation you > produce. Particularly people porting applications. And there are few things > that are less fun than unreliably occurring problems with code one is not > familiar with. Totally agree. In fact I've never said I didn't want to test the implementation. > CU, Ingo > > I'm also attaching a new patch. Log: == old log == - Fixed warnings - Fixed deadlock in xsi_sem_undo - RecordUndo - Fixed issue in xsi_sem_undo: if the semaphore set does not exist anymore, ignore the request but do remove the process from the sUndoList, which wasn't previously done. == plus == - free in ClearUndos was called with interrupts disabled - when a set ends to exist, remove all it's sem_undo request as it's ID will be reused in the futher. Regards, -- Salvatore Benedetto (a.k.a. emitrax) Student of Computer Engineer University of Pisa www.haiku-os.it
Index: src/system/kernel/posix/xsi_semaphore.cpp =================================================================== --- src/system/kernel/posix/xsi_semaphore.cpp (revision 26677) +++ src/system/kernel/posix/xsi_semaphore.cpp (working copy) @@ -133,7 +133,7 @@ int RecordUndo(int semaphoreSetID, short semaphoreNumber, short value); // Implemented after sUndoListLock is declared - int RemoveUndo(int semaphoreSetID, short semaphoreNumber, short value); + void RemoveUndo(int semaphoreSetID, short semaphoreNumber, short value); void Revert(short value) { @@ -256,6 +256,10 @@ ~XsiSemaphoreSet() { + // Clear all sem_undo left, as our ID will be reused + // by another set. + for (uint32 i = 0; i < fNumberOfSemaphores; i++) + fSemaphores[i].ClearUndos(fID, i); UnsetID(); delete []fSemaphores; } @@ -493,16 +497,20 @@ // the global undo list, plus decrementing the related // team xsi_sem_undo_requests field. // This happens only on semctl SETVAL and SETALL. + TRACE(("XsiSemaphore::ClearUndos: semaphoreSetID = %d, " + "semaphoreNumber = %d\n", semaphoreSetID, semaphoreNumber)); MutexLocker _(sUndoListLock); DoublyLinkedList<sem_undo>::Iterator iterator = sUndoList.GetIterator(); while (iterator.HasNext()) { struct sem_undo *current = iterator.Next(); if (current->semaphore_set_id == semaphoreSetID && current->semaphore_number == semaphoreNumber) { - InterruptsSpinLocker _(team_spinlock); + InterruptsSpinLocker lock(team_spinlock); if (current->team) current->team->xsi_sem_undo_requests--; iterator.Remove(); + // Restore interrupts before calling free + lock.Unlock(); free(current); } } @@ -526,7 +534,8 @@ // Update its undo value TRACE(("XsiSemaphore::RecordUndo: found record. Team = %d, " "semaphoreSetID = %d, semaphoreNumber = %d, value = %d\n", - team->id, semaphoreSetID, semaphoreNumber, current->undo_value)); + (int)team->id, semaphoreSetID, semaphoreNumber, + current->undo_value)); int newValue = current->undo_value + value; if (newValue > USHRT_MAX || newValue < -USHRT_MAX) { TRACE_ERROR(("XsiSemaphore::RecordUndo: newValue %d out of range\n", @@ -559,13 +568,14 @@ sUndoList.Add(request); TRACE(("XsiSemaphore::RecordUndo: new record added. Team = %d, " "semaphoreSetID = %d, semaphoreNumber = %d, value = %d\n", - team->id, semaphoreSetID, semaphoreNumber, request->undo_value)); + (int)team->id, semaphoreSetID, semaphoreNumber, + request->undo_value)); } return B_OK; } -int +void XsiSemaphore::RemoveUndo(int semaphoreSetID, short semaphoreNumber, short value) { // This can be called only when RecordUndo fails. @@ -643,6 +653,11 @@ if (numberOfUndos <= 0) return; + // Since we only have one lock for both the semaphore set + // hash table and the semaphore set itself (not worth to add + // a lock per set), we must hold this mutex before the sem_undo + // one in order to avoid deadlock with RecordUndo + MutexLocker lock(sXsiSemaphoreSetLock); MutexLocker _(sUndoListLock); DoublyLinkedList<sem_undo>::Iterator iterator = sUndoList.GetIterator(); // Look for all sem_undo request from this team @@ -651,21 +666,21 @@ if (current->team->id == teamID) { // Check whether the semaphore set still exist int semaphoreSetID = current->semaphore_set_id; - MutexLocker _(sXsiSemaphoreSetLock); XsiSemaphoreSet *semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreSetID); - if (semaphoreSet == NULL) { + if (semaphoreSet != NULL) { + // Revert the changes done by this process + XsiSemaphore *semaphore + = semaphoreSet->Semaphore(current->semaphore_number); + TRACE(("xsi_do_undo: TeamID = %d, SemaphoreSetID = %d, " + "SemaphoreNumber = %d, undo value = %d\n", (int)teamID, + semaphoreSetID, current->semaphore_number, + current->undo_value)); + semaphore->Revert(current->undo_value); + } else TRACE(("xsi_do_undo: semaphore set %d does not exist " "anymore. Ignore record.\n", semaphoreSetID)); - continue; - } - // Revert the changes done by this process - XsiSemaphore *semaphore - = semaphoreSet->Semaphore(current->semaphore_number); - TRACE(("xsi_do_undo: TeamID = %d, SemaphoreSetID = %d, " - "SemaphoreNumber = %d, undo value = %d\n", teamID, - semaphoreSetID, current->semaphore_number, current->undo_value)); - semaphore->Revert(current->undo_value); + // Remove and free the sem_undo structure from sUndoList iterator.Remove(); free(current); @@ -976,7 +991,7 @@ status_t _user_xsi_semop(int semaphoreID, struct sembuf *ops, size_t numOps) { - TRACE(("xsi_semop: semaphoreID = %d, ops = %p, numOps = %d\n", + TRACE(("xsi_semop: semaphoreID = %d, ops = %p, numOps = %ld\n", semaphoreID, ops, numOps)); MutexLocker lock(sXsiSemaphoreSetLock); XsiSemaphoreSet *semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreID); @@ -1021,14 +1036,13 @@ while (notDone) { XsiSemaphore *semaphore = NULL; short numberOfSemaphores = semaphoreSet->NumberOfSemaphores(); - // TODO: Perhaps lock the set itself? bool goToSleep = false; uint32 i = 0; for (; i < numOps; i++) { short semaphoreNumber = operations[i].sem_num; if (semaphoreNumber >= numberOfSemaphores) { - TRACE_ERROR(("xsi_semop: %d invalid semaphore number\n", i)); + TRACE_ERROR(("xsi_semop: %ld invalid semaphore number\n", i)); result = EINVAL; break; } @@ -1100,12 +1114,10 @@ // We acquired the semaphore, now records the sem_undo // requests XsiSemaphore *semaphore = NULL; - short numberOfSemaphores = semaphoreSet->NumberOfSemaphores(); uint32 i = 0; for (; i < numOps; i++) { short semaphoreNumber = operations[i].sem_num; semaphore = semaphoreSet->Semaphore(semaphoreNumber); - unsigned short value = semaphore->Value(); short operation = operations[i].sem_op; if (operations[i].sem_flg & SEM_UNDO) if (semaphore->RecordUndo(semaphoreSet->ID(), @@ -1129,7 +1141,8 @@ result = ENOSPC; } } - // TODO: Also set last PID for this semaphore set + // We did it. Set the pid. + semaphore->SetPid(getpid()); } } return result;
Attachment:
xsi_semaphore_test.jpg
Description: JPEG image