Hi there, attached is a second patch of xsi semaphore implementation. It includes the SEM_UNDO features. I actually spent more time than I though on this one, because the sem_undo list get accesed not only when a process exit, thus executing all its sem_undo request, but also when calling semctl with SETVAL or SETALL on a semaphore (all sem_undo request must be cleared, that is deleted). I reworked it three times in order to keep it as simple as possible and eventually came up with a single global sem_undo list (sUndoList). I wanted to add as little as possible to the team structure. The complexity of the algorithm when removing an element is of course O(n) as I iterated through the list but only a simple short value has been to the team structure (at first it was a boolean value) and speed shouldn't really be a problem as I think we won't have many semaphores in the systems. Anyway, if it happens to be a problem, I'll try with another solution. The code has been tested with bonnie++, which uses the SEM_UNDO feature, and it seems to works fine. I've also fixed some bugs that weren't easy to discover by simple reviewing the code in the first patch and bonnie++ helped with this. In fact it now runs in multiprocesses mode. For those who want to test it, the following run three processes that synchronized themself with the semaphores bonnie++ -p 3 -u 0 bonnie++ -y -u 0 & bonnie++ -y -u 0 & bonnie++ -y -u 0 & I've been running some test with bonnie++ in multiprocesses mode and no file system corruption has happened after last week commits. However the software quits thinking that there is not more space available where there actually is. The same behavior does't happened with dd though. Also some other panic have happened during the test, but not bfs related (at least it seems), like PANIC: _mutex_lock(): double lock of 0x90cc4ed0 by thread 3595 where the mutex is vm_cache and thread is grep Anyway, I'll investigate on these bugs once this code is complete and committed. Regards, -- Salvatore Benedetto (a.k.a. emitrax) Student of Computer Engineer University of Pisa www.haiku-os.it
Index: src/system/kernel/main.cpp =================================================================== --- src/system/kernel/main.cpp (revision 26666) +++ src/system/kernel/main.cpp (working copy) @@ -37,6 +37,7 @@ #include <Notifications.h> #include <port.h> #include <posix/realtime_sem.h> +#include <posix/xsi_semaphore.h> #include <real_time_clock.h> #include <sem.h> #include <smp.h> @@ -174,7 +175,9 @@ TRACE("init kernel daemons\n"); kernel_daemon_init(); arch_platform_init_post_thread(&sKernelArgs); + TRACE("init posix semaphores\n"); realtime_sem_init(); + xsi_ipc_init(); TRACE("init VM threads\n"); vm_init_post_thread(&sKernelArgs); Index: src/system/kernel/posix/Jamfile =================================================================== --- src/system/kernel/posix/Jamfile (revision 26666) +++ src/system/kernel/posix/Jamfile (working copy) @@ -4,6 +4,7 @@ KernelMergeObject kernel_posix.o : realtime_sem.cpp + xsi_semaphore.cpp : $(TARGET_KERNEL_PIC_CCFLAGS) ; Index: src/system/kernel/posix/xsi_semaphore.cpp =================================================================== --- src/system/kernel/posix/xsi_semaphore.cpp (revision 0) +++ src/system/kernel/posix/xsi_semaphore.cpp (revision 0) @@ -0,0 +1,1128 @@ +/* + * Copyright 2008, Haiku Inc. All rights reserved. + * Distributed under the terms of the MIT License. + * + * Authors: + * Salvatore Benedetto <salvatore.benedetto@xxxxxxxxx> + */ + +#include <posix/xsi_semaphore.h> + +#include <new> + +#include <sys/ipc.h> +#include <sys/types.h> + +#include <OS.h> + +#include <kernel.h> +#include <syscall_restart.h> + +#include <util/AutoLock.h> +#include <util/DoublyLinkedList.h> +#include <util/OpenHashTable.h> +#include <util/Vector.h> + + +#define TRACE_XSI_SEM +#ifdef TRACE_XSI_SEM +# define TRACE(x) dprintf x +# define TRACE_ERROR(x) dprintf x +#else +# define TRACE(x) /* nothing */ +# define TRACE_ERROR(x) dprintf x +#endif + +//#define KTRACE_XSI_SEM +#ifdef KTRACE_XSI_SEM +# define KTRACE(x...) ktrace_printf(x) +#else +# define KTRACE(x...) +#endif + +// Queue for holding blocked threads +struct queued_thread : DoublyLinkedListLinkImpl<queued_thread> { + queued_thread(struct thread *thread, int32 count) + : + thread(thread), + count(count), + queued(false) + { + } + + struct thread *thread; + int32 count; + bool queued; +}; + +typedef DoublyLinkedList<queued_thread> ThreadQueue; + +struct sem_undo : DoublyLinkedListLinkImpl<sem_undo> { + sem_undo(struct team *process, int semaphoreSetID, short semaphoreNumber, + short undoValue) + : + team(process), + semaphore_set_id(semaphoreSetID), + semaphore_number(semaphoreNumber), + undo_value(undoValue) + { + } + + struct team *team; + int semaphore_set_id; + short semaphore_number; + short undo_value; +}; + +typedef DoublyLinkedList<sem_undo> SemaphoreUndoList; + +// Xsi semaphore definition +class XsiSemaphore { +public: + XsiSemaphore() + : fLastPidOperation(0), + fThreadsWaitingToIncrease(0), + fThreadsWaitingToBeZero(0), + fValue(0) + { + } + + ~XsiSemaphore() + { + // For some reason the semaphore is getting destroyed. + // Wake up any remaing awaiting threads + InterruptsSpinLocker _(thread_spinlock); + while (queued_thread *entry = fWaitingToIncreaseQueue.RemoveHead()) { + entry->queued = false; + thread_unblock_locked(entry->thread, EIDRM); + } + while (queued_thread *entry = fWaitingToBeZeroQueue.RemoveHead()) { + entry->queued = false; + thread_unblock_locked(entry->thread, EIDRM); + } + // No need to remove any sem_undo request still + // hanging. When the process exit and doesn't found + // the semaphore set, it'll just ignore the sem_undo + // request. That's better than iterating trough the + // whole sUndoList. Beside we don't know our semaphore + // number nor our semaphore set id. + } + + // We return true in case the operation causes the + // caller to wait, so it can undo all the operations + // previously done + bool Add(short value) + { + if ((int)(fValue + value) < 0) { + TRACE(("XsiSemaphore::Add: potentially going to sleep\n")); + return true; + } else { + fValue += value; + if (fValue == 0 && fThreadsWaitingToBeZero > 0) + WakeUpThread(true); + else if (fValue > 0 && fThreadsWaitingToIncrease > 0) + WakeUpThread(false); + return false; + } + } + + // Implemented after sUndoListLock is declared + void ClearUndos(int semaphoreSetID, short semaphoreNumber); + + pid_t LastPid() const + { + return fLastPidOperation; + } + + // Record the sem_undo operation in sUndoList. The only limit + // here is the memory needed for creating a new sem_undo structure. + // Implemented after sUndoListLock is declared + int RecordUndo(int semaphoreSetID, short semaphoreNumber, short value); + + // Implemented after sUndoListLock is declared + int RemoveUndo(int semaphoreSetID, short semaphoreNumber, short value); + + void Revert(short value) + { + fValue -= value; + } + + void SetPid(pid_t pid) + { + fLastPidOperation = pid; + } + + void SetValue(ushort value) + { + fValue = value; + } + + ushort ThreadsWaitingToIncrease() const + { + return fThreadsWaitingToIncrease; + } + + ushort ThreadsWaitingToBeZero() const + { + return fThreadsWaitingToBeZero; + } + + ushort Value() const + { + return fValue; + } + + status_t Wait(int32 count, bool waitForZero) + { + TRACE(("XsiSemaphore::Wait: going to sleep\n")); + // enqueue the thread in the appropriate + // queue and get ready to wait + struct thread *thread = thread_get_current_thread(); + queued_thread queueEntry(thread, count); + if (waitForZero) { + fWaitingToBeZeroQueue.Add(&queueEntry); + fThreadsWaitingToBeZero++; + } else { + fWaitingToIncreaseQueue.Add(&queueEntry); + fThreadsWaitingToIncrease++; + } + queueEntry.queued = true; + + thread_prepare_to_block(thread, B_CAN_INTERRUPT, + THREAD_BLOCK_TYPE_OTHER, (void*)"xsi semaphore"); + + InterruptsSpinLocker _(thread_spinlock); + status_t result = thread_block_locked(thread); + + if (queueEntry.queued) { + // If we are still queued, we failed to acquire + // the semaphore for some reason + if (waitForZero) { + fWaitingToBeZeroQueue.Remove(&queueEntry); + fThreadsWaitingToBeZero--; + } else { + fWaitingToIncreaseQueue.Remove(&queueEntry); + fThreadsWaitingToIncrease--; + } + } + + return result; + } + + void WakeUpThread(bool waitingForZero) + { + InterruptsSpinLocker _(thread_spinlock); + if (waitingForZero) { + // Wake up all threads waiting on zero + while (queued_thread *entry = fWaitingToBeZeroQueue.RemoveHead()) { + entry->queued = false; + fThreadsWaitingToBeZero--; + thread_unblock_locked(entry->thread, 0); + } + } else { + // Wake up all threads even though they might go back to sleep + while (queued_thread *entry = fWaitingToIncreaseQueue.RemoveHead()) { + entry->queued = false; + fThreadsWaitingToIncrease--; + thread_unblock_locked(entry->thread, 0); + } + } + } + +private: + pid_t fLastPidOperation; // sempid + ushort fThreadsWaitingToIncrease; // semncnt + ushort fThreadsWaitingToBeZero; // semzcnt + ushort fValue; // semval + + ThreadQueue fWaitingToIncreaseQueue; + ThreadQueue fWaitingToBeZeroQueue; +}; + +#define MAX_XSI_SEMS_PER_TEAM 128 + +// Xsi semaphore set definition (semid_ds) +class XsiSemaphoreSet { +public: + XsiSemaphoreSet(int numberOfSemaphores, int flags) + : fInitOK(false), + fLastSemctlTime((time_t)real_time_clock()), + fLastSemopTime(0), + fNumberOfSemaphores(numberOfSemaphores), + fSemaphores(0) + { + SetIpcKey((key_t)-1); + SetPermissions(flags); + fSemaphores = new(std::nothrow) XsiSemaphore[numberOfSemaphores]; + if (fSemaphores == NULL) { + TRACE_ERROR(("XsiSemaphoreSet::XsiSemaphore(): failed to allocate " + "XsiSemaphore object\n")); + } else + fInitOK = true; + } + + ~XsiSemaphoreSet() + { + UnsetID(); + delete []fSemaphores; + } + + void DoIpcSet(struct semid_ds *result) + { + fPermissions.uid = result->sem_perm.uid; + fPermissions.gid = result->sem_perm.gid; + fPermissions.mode = (fPermissions.mode & ~0x01ff) + | (result->sem_perm.mode & 0x01ff); + } + + bool HasPermission() const + { + if ((fPermissions.mode & S_IWOTH) != 0) + return true; + + uid_t uid = geteuid(); + if (uid == 0 || (uid == fPermissions.uid + && (fPermissions.mode & S_IWUSR) != 0)) + return true; + + gid_t gid = getegid(); + if (gid == fPermissions.gid && (fPermissions.mode & S_IWGRP) != 0) + return true; + + return false; + } + + bool HasReadPermission() const + { + // TODO: fix this + return HasPermission(); + } + + int ID() const + { + return fID; + } + + bool InitOK() + { + return fInitOK; + } + + key_t IpcKey() const + { + return fPermissions.key; + } + + struct ipc_perm IpcPermission() const + { + return fPermissions; + } + + time_t LastSemctlTime() const + { + return fLastSemctlTime; + } + + time_t LastSemopTime() const + { + return fLastSemopTime; + } + + ushort NumberOfSemaphores() const + { + return fNumberOfSemaphores; + } + + XsiSemaphore* Semaphore(int nth) const + { + return &fSemaphores[nth]; + } + + // Implemented after sSemaphoreHashTable is declared + void SetID(); + + void SetIpcKey(key_t key) + { + fPermissions.key = key; + } + + void SetLastSemctlTime() + { + fLastSemctlTime = real_time_clock(); + } + + void SetLastSemopTime() + { + fLastSemopTime = real_time_clock(); + } + + void SetPermissions(int flags) + { + fPermissions.uid = fPermissions.cuid = geteuid(); + fPermissions.gid = fPermissions.cgid = getegid(); + fPermissions.mode = (flags & 0x01ff); + } + + // Implemented after sSemaphoreHashTable is declared + void UnsetID(); + + HashTableLink<XsiSemaphoreSet>* Link() + { + return &fLink; + } + +private: + bool fInitOK; + int fID; // semaphore set id + time_t fLastSemctlTime; // sem_ctime + time_t fLastSemopTime; // sem_otime + ushort fNumberOfSemaphores; // sem_nsems + struct ipc_perm fPermissions; // sem_perm + XsiSemaphore *fSemaphores; + + ::HashTableLink<XsiSemaphoreSet> fLink; +}; + +// Xsi semaphore set hash table +struct SemaphoreHashTableDefinition { + typedef int KeyType; + typedef XsiSemaphoreSet ValueType; + + size_t HashKey (const int key) const + { + return (size_t)key; + } + size_t Hash(XsiSemaphoreSet *variable) const + { + return (size_t)variable->ID(); + } + bool Compare(const int key, XsiSemaphoreSet *variable) const + { + return (int)key == (int)variable->ID(); + } + HashTableLink<XsiSemaphoreSet>* GetLink(XsiSemaphoreSet *variable) const + { + return variable->Link(); + } +}; + + +// IPC class +class Ipc { +public: + Ipc(key_t key) + : fKey(key), + fSemaphoreSetId(-1) + { + } + + key_t Key() const + { + return fKey; + } + + int SemaphoreSetID() const + { + return fSemaphoreSetId; + } + + void SetSemaphoreSetID(XsiSemaphoreSet *semaphoreSet) + { + fSemaphoreSetId = semaphoreSet->ID(); + } + + bool HasSemaphoreSet() + { + if (fSemaphoreSetId != -1) + return true; + return false; + } + + HashTableLink<Ipc>* Link() + { + return &fLink; + } + +private: + key_t fKey; + int fSemaphoreSetId; + HashTableLink<Ipc> fLink; +}; + + +struct IpcHashTableDefinition { + typedef key_t KeyType; + typedef Ipc ValueType; + + size_t HashKey (const key_t key) const + { + return (size_t)(key); + } + size_t Hash(Ipc *variable) const + { + return (size_t)HashKey(variable->Key()); + } + bool Compare(const key_t key, Ipc *variable) const + { + return (key_t)key == (key_t)variable->Key(); + } + HashTableLink<Ipc>* GetLink(Ipc *variable) const + { + return variable->Link(); + } +}; + +// Arbitrary limit +#define MAX_XSI_SEMAPHORE 512 +static OpenHashTable<IpcHashTableDefinition> sIpcHashTable; +static OpenHashTable<SemaphoreHashTableDefinition> sSemaphoreHashTable; +static SemaphoreUndoList sUndoList; + +static mutex sIpcLock; +static mutex sXsiSemaphoreSetLock; +static mutex sUndoListLock; + +static vint32 sNextAvailableID = 1; +static vint32 sXsiSemaphoreCount = 0; + + +void +XsiSemaphore::ClearUndos(int semaphoreSetID, short semaphoreNumber) +{ + // Clear all undo_value (Posix semadj equivalent), + // which result in removing the sem_undo record from + // the global undo list, plus decrementing the related + // team xsi_sem_undo_requests field. + // This happens only on semctl SETVAL and SETALL. + 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); + if (current->team) + current->team->xsi_sem_undo_requests--; + iterator.Remove(); + free(current); + } + } +} + + +int +XsiSemaphore::RecordUndo(int semaphoreSetID, short semaphoreNumber, short value) +{ + // Look if there is already a record from the same + // team for the same semaphore set && semaphore number + bool notFound = true; + struct team *team = thread_get_current_thread()->team; + MutexLocker _(sUndoListLock); + DoublyLinkedList<sem_undo>::Iterator iterator = sUndoList.GetIterator(); + while (iterator.HasNext()) { + struct sem_undo *current = iterator.Next(); + if (current->team == team + && current->semaphore_set_id == semaphoreSetID + && current->semaphore_number == semaphoreNumber) { + // 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 newValue = current->undo_value + value; + if (newValue > USHRT_MAX || newValue < -USHRT_MAX) { + TRACE_ERROR(("XsiSemaphore::RecordUndo: newValue %d out of range\n", + newValue)); + return ERANGE; + } + current->undo_value = newValue; + notFound = false; + break; + } + } + + if (notFound) { + // First sem_undo request from this team for this + // semaphore set && semaphore number + struct sem_undo *request + = (struct sem_undo *)malloc(sizeof(struct sem_undo)); + if (request == NULL) + return B_NO_MEMORY; + request->team = team; + request->semaphore_set_id = semaphoreSetID; + request->semaphore_number = semaphoreNumber; + request->undo_value = value; + // Add the request to the global sem_undo list + InterruptsSpinLocker _(team_spinlock); + if ((int)(team->xsi_sem_undo_requests + 1) < USHRT_MAX) + team->xsi_sem_undo_requests++; + else + return ENOSPC; + 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)); + } + return B_OK; +} + + +int +XsiSemaphore::RemoveUndo(int semaphoreSetID, short semaphoreNumber, short value) +{ + // This can be called only when RecordUndo fails. + 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) { + current->undo_value -= value; + // Remove the request from sUndoList only if + // it happens to be the only one made by this + // process, that is, don't remove any valide + // sem_undo request made previously by the same + // process + if (current->undo_value == 0) { + InterruptsSpinLocker _(team_spinlock); + if (current->team) + current->team->xsi_sem_undo_requests--; + iterator.Remove(); + free(current); + } + } + } +} + + +void +XsiSemaphoreSet::SetID() +{ + // The lock is held before calling us + while (true) { + if (sSemaphoreHashTable.Lookup(sNextAvailableID) == NULL) + break; + sNextAvailableID++; + } + fID = sNextAvailableID++; +} + + +void +XsiSemaphoreSet::UnsetID() +{ + sNextAvailableID = fID; +} + + +void +xsi_ipc_init() +{ + // Initialize hash tables + status_t status = sIpcHashTable.Init(); + if (status != B_OK) + panic("xsi_ipc_init() failed to initialized ipc hash table\n"); + status = sSemaphoreHashTable.Init(); + if (status != B_OK) + panic("xsi_ipc_init() failed to initialized semaphore hash table\n"); + + mutex_init(&sIpcLock, "global Posix IPC table"); + mutex_init(&sXsiSemaphoreSetLock, "global Posix xsi sem table"); + mutex_init(&sUndoListLock, "global Posix xsi sem undo list"); +} + + +// Function called on team exit when there are +// sem_undo requests +void +xsi_do_undo(team_id teamID, short numberOfUndos) +{ + MutexLocker _(sUndoListLock); + DoublyLinkedList<sem_undo>::Iterator iterator = sUndoList.GetIterator(); + // Look for all sem_undo request from this team + while (iterator.HasNext()) { + struct sem_undo *current = iterator.Next(); + 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) { + 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); + if (--numberOfUndos == 0) + break; + } + } +} + + +int +_user_xsi_semget(key_t key, int numberOfSemaphores, int flags) +{ + TRACE(("xsi_semget: key = %d, numberOfSemaphores = %d, flags = %d\n", + (int)key, numberOfSemaphores, flags)); + XsiSemaphoreSet *semaphoreSet = NULL; + Ipc *ipcKey = NULL; + // Default assumptions + bool isPrivate = true; + bool create = true; + + MutexLocker _(sIpcLock); + if (key != IPC_PRIVATE) { + isPrivate = false; + // Check if key already has a semaphore associated with it + ipcKey = sIpcHashTable.Lookup(key); + if (ipcKey == NULL) { + // The ipc key have probably just been created + // by the caller, add it to the system + ipcKey = new(std::nothrow) Ipc(key); + if (ipcKey == NULL) { + TRACE_ERROR(("xsi_semget: failed to create new Ipc object " + "for key %d\n", (int)key)); + return ENOMEM; + } + sIpcHashTable.Insert(ipcKey); + } else if (ipcKey->HasSemaphoreSet()) { + // The IPC key exist and it already has a semaphore + if ((flags & IPC_CREAT) && (flags & IPC_EXCL)) { + TRACE_ERROR(("xsi_semget: key %d already exist\n", (int)key)); + return EEXIST; + } + int semaphoreSetID = ipcKey->SemaphoreSetID(); + + MutexLocker _(sXsiSemaphoreSetLock); + semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreSetID); + if (!semaphoreSet->HasPermission()) { + TRACE_ERROR(("xsi_semget: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + if (numberOfSemaphores > semaphoreSet->NumberOfSemaphores() + && numberOfSemaphores != 0) { + TRACE_ERROR(("xsi_semget: numberOfSemaphores greater than the " + "one associated with semaphore %d, key %d\n", + semaphoreSet->ID(), (int)semaphoreSet->IpcKey())); + return EINVAL; + } + create = false; + } else { + // The IPC key exist but it has not semaphore associated with it + if (!(flags & IPC_CREAT)) { + TRACE_ERROR(("xsi_semget: key %d has not semaphore associated " + "with it and caller did not ask for creation\n",(int)key)); + return ENOENT; + } + } + } else { + // TODO: Handle case of private key + } + + if (create) { + // Create a new sempahore set for this key + if (numberOfSemaphores < 0 + || numberOfSemaphores >= MAX_XSI_SEMS_PER_TEAM) { + TRACE_ERROR(("xsi_semget: numberOfSemaphores out of range\n")); + return EINVAL; + } + if (sXsiSemaphoreCount >= MAX_XSI_SEMAPHORE) { + TRACE_ERROR(("xsi_semget: reached limit of maximum number of " + "semaphores allowed\n")); + return ENOSPC; + } + atomic_add(&sXsiSemaphoreCount, 1); + + semaphoreSet = new(std::nothrow) XsiSemaphoreSet(numberOfSemaphores, + flags); + if (semaphoreSet == NULL || !semaphoreSet->InitOK()) { + TRACE_ERROR(("xsi_semget: failed to allocate a new xsi " + "semaphore set\n")); + atomic_add(&sXsiSemaphoreCount, -1); + return ENOMEM; + } + + MutexLocker _(sXsiSemaphoreSetLock); + semaphoreSet->SetID(); + if (isPrivate) + semaphoreSet->SetIpcKey((key_t)-1); + else { + semaphoreSet->SetIpcKey(key); + ipcKey->SetSemaphoreSetID(semaphoreSet); + } + sSemaphoreHashTable.Insert(semaphoreSet); + } + + return semaphoreSet->ID(); +} + + +int +_user_xsi_semctl(int semaphoreID, int semaphoreNumber, int command, + union semun *args) +{ + TRACE(("xsi_semctl: semaphoreID = %d, semaphoreNumber = %d, command = %d\n", + semaphoreID, semaphoreNumber, command)); + MutexLocker _(sXsiSemaphoreSetLock); + XsiSemaphoreSet *semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreID); + if (semaphoreSet == NULL) { + TRACE_ERROR(("xsi_semctl: semaphore set id %d not valid\n", + semaphoreID)); + return EINVAL; + } + if (semaphoreNumber < 0 + || semaphoreNumber > semaphoreSet->NumberOfSemaphores()) { + TRACE_ERROR(("xsi_semctl: semaphore number %d not valid for " + "semaphore %d\n", semaphoreNumber, semaphoreID)); + return EINVAL; + } + + if (args != 0 && !IS_USER_ADDRESS(args)) { + TRACE_ERROR(("xsi_semctl: semun address is not valid\n")); + return B_BAD_ADDRESS; + } + + XsiSemaphore *semaphore = semaphoreSet->Semaphore(semaphoreNumber); + switch (command) { + case GETVAL: + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + return semaphore->Value(); + + case SETVAL: + if (!semaphoreSet->HasPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + int value; + if (user_memcpy(&value, &args->val, sizeof(int)) < B_OK) { + TRACE_ERROR(("xsi_semctl: user_memcpy failed\n")); + return B_BAD_ADDRESS; + } + if (value > USHRT_MAX) { + TRACE_ERROR(("xsi_semctl: value %d out of range\n", value)); + return ERANGE; + } + TRACE(("xsi_semctl: SemaphoreNumber = %d, SETVAL value = %d\n", + semaphoreNumber, value)); + semaphore->SetValue(value); + semaphore->ClearUndos(semaphoreSet->ID(), semaphoreNumber); + return 0; + + case GETPID: + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + return semaphore->LastPid(); + + case GETNCNT: + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + return semaphore->ThreadsWaitingToIncrease(); + + case GETZCNT: + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + return semaphore->ThreadsWaitingToBeZero(); + + case GETALL: { + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not read " + "permission on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + for (int i = 0; i < semaphoreSet->NumberOfSemaphores(); i++) { + semaphore = semaphoreSet->Semaphore(i); + unsigned short value = semaphore->Value(); + if (user_memcpy(&args->array[i], &value, sizeof(unsigned short)) + < B_OK) { + TRACE_ERROR(("xsi_semctl: user_memcpy failed\n")); + return B_BAD_ADDRESS; + } + } + return 0; + } + + case SETALL: { + if (!semaphoreSet->HasPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not permission " + "on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + for (int i = 0; i < semaphoreSet->NumberOfSemaphores(); i++) { + semaphore = semaphoreSet->Semaphore(i); + unsigned short value; + if (user_memcpy(&value, &args->array[i], sizeof(unsigned short)) + < B_OK) { + TRACE_ERROR(("xsi_semctl: user_memcpy failed\n")); + return B_BAD_ADDRESS; + } + semaphore->SetValue(value); + semaphore->ClearUndos(semaphoreSet->ID(), semaphoreNumber); + } + return 0; + } + + case IPC_STAT: { + if (!semaphoreSet->HasReadPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not read " + "permission on semaphore %d, key %d\n", semaphoreSet->ID(), + (int)semaphoreSet->IpcKey())); + return EACCES; + } + struct semid_ds result; + result.sem_perm = semaphoreSet->IpcPermission(); + result.sem_nsems = semaphoreSet->NumberOfSemaphores(); + result.sem_otime = semaphoreSet->LastSemopTime(); + result.sem_ctime = semaphoreSet->LastSemctlTime(); + if (user_memcpy(args->buf, &result, sizeof(struct semid_ds)) + < B_OK) { + TRACE_ERROR(("xsi_semctl: user_memcpy failed\n")); + return B_BAD_ADDRESS; + } + return 0; + } + + case IPC_SET: { + if (!semaphoreSet->HasPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not " + "permission on semaphore %d, key %d\n", + semaphoreSet->ID(), (int)semaphoreSet->IpcKey())); + return EACCES; + } + struct semid_ds result; + if (user_memcpy(&result, args->buf, sizeof(struct semid_ds)) + < B_OK) { + TRACE_ERROR(("xsi_semctl: user_memcpy failed\n")); + return B_BAD_ADDRESS; + } + semaphoreSet->DoIpcSet(&result); + return 0; + } + + case IPC_RMID: { + if (!semaphoreSet->HasPermission()) { + TRACE_ERROR(("xsi_semctl: calling process has not " + "permission on semaphore %d, key %d\n", + semaphoreSet->ID(), (int)semaphoreSet->IpcKey())); + return EACCES; + } + key_t key = semaphoreSet->IpcKey(); + Ipc *ipcKey = NULL; + if (key != -1) { + MutexLocker _(sIpcLock); + ipcKey = sIpcHashTable.Lookup(key); + sIpcHashTable.Remove(ipcKey); + } + sSemaphoreHashTable.Remove(semaphoreSet); + atomic_add(&sXsiSemaphoreCount, + semaphoreSet->NumberOfSemaphores()); + // Wake up of threads waiting on this set + // happens in the destructor + if (key != -1) + delete ipcKey; + delete semaphoreSet; + return 0; + } + + default: + TRACE_ERROR(("xsi_semctl: command %d not valid\n", command)); + return EINVAL; + } +} + + +status_t +_user_xsi_semop(int semaphoreID, struct sembuf *ops, size_t numOps) +{ + TRACE(("xsi_semop: semaphoreID = %d, ops = %p, numOps = %d\n", + semaphoreID, ops, numOps)); + MutexLocker lock(sXsiSemaphoreSetLock); + XsiSemaphoreSet *semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreID); + if (semaphoreSet == NULL) { + TRACE_ERROR(("xsi_semop: semaphore set id %d not valid\n", + semaphoreID)); + return EINVAL; + } + + if (!IS_USER_ADDRESS(ops)) { + TRACE_ERROR(("xsi_semop: sembuf address is not valid\n")); + return B_BAD_ADDRESS; + } + + if (numOps < 0 || numOps >= MAX_XSI_SEMS_PER_TEAM) { + TRACE_ERROR(("xsi_semop: numOps out of range\n")); + return EINVAL; + } + + struct sembuf *operations + = (struct sembuf *)malloc(sizeof(struct sembuf) * numOps); + if (operations == NULL) { + TRACE_ERROR(("xsi_semop: failed to allocate sembuf struct\n")); + return B_NO_MEMORY; + } + + if (user_memcpy(operations, ops, + (sizeof(struct sembuf) * numOps)) < B_OK) { + TRACE_ERROR(("xsi_semop: user_memcpy failed\n")); + free(operations); + return B_BAD_ADDRESS; + } + + /* + * We won't do partial request, that is operations + * only on some sempahores belonging to the set and then + * going to sleep. If we must wait on a semaphore, we undo + * all the operations already done and go to sleep, otherwise + * we may caused some unwanted deadlock among threads + * fighting for the same set. + */ + bool notDone = true; + status_t result = 0; + 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)); + result = EINVAL; + break; + } + semaphore = semaphoreSet->Semaphore(semaphoreNumber); + unsigned short value = semaphore->Value(); + short operation = operations[i].sem_op; + TRACE(("xsi_semop: semaphoreNumber = %d, value = %d\n", + semaphoreNumber, value)); + if (operation < 0) { + if (semaphore->Add(operation)) { + if (operations[i].sem_flg & IPC_NOWAIT) + result = EAGAIN; + else + goToSleep = true; + break; + } + } else if (operation == 0) { + if (value == 0) + continue; + else if (operations[i].sem_flg & IPC_NOWAIT) { + result = EAGAIN; + break; + } else { + goToSleep = true; + break; + } + } else { + // Operation must be greater than zero, + // just add the value and continue + semaphore->Add(operation); + } + } + + // Either we have to wait or an error occured + if (goToSleep || result != 0) { + // Undo all previously done operations + for (uint32 j = 0; j < i; j++) { + short semaphoreNumber = operations[j].sem_num; + semaphore = semaphoreSet->Semaphore(semaphoreNumber); + short operation = operations[j].sem_op; + if (operation != 0) + semaphore->Revert(operation); + } + if (result != 0) + return result; + + bool waitOnZero = true; + if (operations[i].sem_op != 0) + waitOnZero = false; + + lock.Unlock(); + result = semaphore->Wait((int32)operations[i].sem_op, waitOnZero); + TRACE(("xsi_semop: back to life\n")); + + // We are back to life. + // Find out why! + lock.Lock(); + semaphoreSet = sSemaphoreHashTable.Lookup(semaphoreID); + if (result == EIDRM || result == B_INTERRUPTED) { + TRACE_ERROR(("xsi_semop: semaphore set id %d got destroyed\n", + semaphoreID)); + result = EIDRM; + notDone = false; + } + } else { + // everything worked like a charm (so far) + notDone = false; + TRACE(("xsi_semop: semaphore acquired succesfully\n")); + // 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(), + semaphoreNumber, operation) != B_OK) { + // Unlikely scenario, but we might get here. + // Undo everything! + // Start with semaphore operations + for (uint32 j = 0; j < numOps; j++) { + short semaphoreNumber = operations[j].sem_num; + semaphore = semaphoreSet->Semaphore(semaphoreNumber); + short operation = operations[j].sem_op; + if (operation != 0) + semaphore->Revert(operation); + } + // Remove all previously registered sem_undo request + for (uint32 j = 0; j < i; j++) { + if (operations[j].sem_flg & SEM_UNDO) + semaphore->RemoveUndo(semaphoreSet->ID(), + operations[j].sem_num, operations[j].sem_op); + } + result = ENOSPC; + } + } + // TODO: Also set last PID for this semaphore set + } + } + return result; +} Index: src/system/kernel/team.cpp =================================================================== --- src/system/kernel/team.cpp (revision 26666) +++ src/system/kernel/team.cpp (working copy) @@ -31,6 +31,7 @@ #include <ksignal.h> #include <port.h> #include <posix/realtime_sem.h> +#include <posix/xsi_semaphore.h> #include <sem.h> #include <syscall_process_info.h> #include <syscall_restart.h> @@ -699,6 +700,7 @@ team->io_context = NULL; team->address_space = NULL; team->realtime_sem_context = NULL; + team->xsi_sem_undo_requests = 0; team->thread_list = NULL; team->main_thread = NULL; team->loading_info = NULL; @@ -1322,6 +1324,8 @@ delete_team_user_data(team); vm_delete_areas(team->address_space); + if (team->xsi_sem_undo_requests) + xsi_do_undo(team->id, team->xsi_sem_undo_requests); delete_owned_ports(team->id); sem_delete_owned_sems(team->id); remove_images(team); @@ -2338,6 +2342,8 @@ vfs_free_io_context(team->io_context); delete_realtime_sem_context(team->realtime_sem_context); + if (team->xsi_sem_undo_requests) + xsi_do_undo(teamID, team->xsi_sem_undo_requests); delete_owned_ports(teamID); sem_delete_owned_sems(teamID); remove_images(team); Index: src/system/kernel/syscalls.cpp =================================================================== --- src/system/kernel/syscalls.cpp (revision 26666) +++ src/system/kernel/syscalls.cpp (working copy) @@ -17,6 +17,7 @@ #include <vm.h> #include <thread.h> #include <posix/realtime_sem.h> +#include <posix/xsi_semaphore.h> #include <sem.h> #include <port.h> #include <cpu.h> Index: src/system/libroot/posix/sys/ftok.c =================================================================== --- src/system/libroot/posix/sys/ftok.c (revision 0) +++ src/system/libroot/posix/sys/ftok.c (revision 0) @@ -0,0 +1,22 @@ +/* + * Copyright 2008, Haiku Inc. All rights reserved. + * Distributed under the terms of the MIT License. + * + * Authors: + * Salvatore Benedetto <salvatore.benedetto@xxxxxxxxx> + */ + +#include <sys/ipc.h> +#include <sys/types.h> +#include <sys/stat.h> + +key_t +ftok(const char *path, int id) +{ + struct stat st; + + if (stat(path,&st) < 0) + return (key_t)-1; + + return (key_t)(id << 24 | (st.st_dev & 0xff) << 16 | (st.st_ino & 0xffff)); +} Index: src/system/libroot/posix/sys/xsi_sem.cpp =================================================================== --- src/system/libroot/posix/sys/xsi_sem.cpp (revision 0) +++ src/system/libroot/posix/sys/xsi_sem.cpp (revision 0) @@ -0,0 +1,75 @@ +/* + * Copyright 2008, Haiku Inc. All rights reserved. + * Distributed under the terms of the MIT License. + * + * Authors: + * Salvatore Benedetto <salvatore.benedetto@xxxxxxxxx> + */ + +#include <sys/sem.h> + +#include <errno.h> +#include <fcntl.h> +#include <stdarg.h> +#include <stdlib.h> + +#include <OS.h> + +#include <posix/realtime_sem_defs.h> +#include <syscall_utils.h> +#include <syscalls.h> + + +/* + * For the semctl option argument, the user + * should declare explicitly the following union + */ +union semun { + int val; + struct semid_ds *buf; + unsigned short *array; +}; + + +int +semget(key_t key, int num_sems, int sem_flags) +{ + RETURN_AND_SET_ERRNO(_kern_xsi_semget(key, num_sems, sem_flags)); +} + + +int +semctl(int semId, int sem_num, int command, ...) +{ + union semun arg; + va_list args; + + switch (command) { + case GETVAL: + case GETPID: + case GETNCNT: + case GETZCNT: + case IPC_RMID: + RETURN_AND_SET_ERRNO(_kern_xsi_semctl(semId, sem_num, command, 0)); + + case SETVAL: + case GETALL: + case SETALL: + case IPC_STAT: + case IPC_SET: + va_start(args, command); + arg = va_arg(args, union semun); + va_end(args); + RETURN_AND_SET_ERRNO(_kern_xsi_semctl(semId, sem_num, command, + &arg)); + default: + return EINVAL; + } +} + + +int +semop(int sem_id, struct sembuf *sem_ops, size_t num_sem_ops) +{ + RETURN_AND_SET_ERRNO(_kern_xsi_semop(sem_id, sem_ops, num_sem_ops)); +} Index: src/system/libroot/posix/sys/Jamfile =================================================================== --- src/system/libroot/posix/sys/Jamfile (revision 26666) +++ src/system/libroot/posix/sys/Jamfile (working copy) @@ -7,6 +7,7 @@ chmod.c flock.c ftime.c + ftok.c getrusage.c gettimeofday.c itimer.c @@ -23,4 +24,5 @@ uname.c utimes.c wait.c + xsi_sem.cpp ; Index: headers/posix/sys/ipc.h =================================================================== --- headers/posix/sys/ipc.h (revision 26666) +++ headers/posix/sys/ipc.h (working copy) @@ -6,8 +6,8 @@ #define _SYS_IPC_H +#include <sys/cdefs.h> #include <sys/types.h> -#error functionality has not yet been implemented /* Mode bits for msgget(), semget(), and shmget() */ @@ -17,15 +17,15 @@ /* Control commands for msgctl(), semctl(), and shmctl() */ #define IPC_RMID 0 /* remove identifier */ -#define IPC_SET 1 -#define IPC_STAT 2 +#define IPC_SET 1 /* set options */ +#define IPC_STAT 2 /* get options */ /* Private key */ -#define IPC_PRIVATE 0 +#define IPC_PRIVATE (key_t)0 struct ipc_perm { - key_t key; + key_t key; /* IPC identifier */ uid_t uid; /* owner's user ID */ gid_t gid; /* owner's group ID */ uid_t cuid; /* creator's user ID */ @@ -34,14 +34,10 @@ }; -#ifdef __cplusplus -extern "C" { -#endif +__BEGIN_DECLS key_t ftok(const char *path, int id); -#ifdef __cplusplus -} -#endif +__END_DECLS #endif /* _SYS_IPC_H */ Index: headers/posix/sys/sem.h =================================================================== --- headers/posix/sys/sem.h (revision 0) +++ headers/posix/sys/sem.h (revision 0) @@ -0,0 +1,65 @@ +/* + * Copyright 2008, Haiku Inc. All Rights Reserved. + * Distributed under the terms of the MIT License. + */ +#ifndef _SYS_SEM_H +#define _SYS_SEM_H + +#include <sys/cdefs.h> +#include <sys/ipc.h> +#include <sys/types.h> + + +/* Semaphore operation flags */ +#define SEM_UNDO 10 + +/* Command definition for semctl */ +#define GETPID 3 /* Get process ID of last element manipulating */ +#define GETVAL 4 /* Get semval */ +#define GETALL 5 /* Get all semval */ +#define GETNCNT 6 /* Get semncnt */ +#define GETZCNT 7 /* Get semzcnt */ +#define SETVAL 8 /* Set semval */ +#define SETALL 9 /* Set all semval */ + +struct semid_ds { + struct ipc_perm sem_perm; /* Operation permission structure */ + unsigned short sem_nsems; /* Number of semaphores in set */ + time_t sem_otime; /* Last semop */ + time_t sem_ctime; /* Last time changed by semctl */ +}; + +/* Structure passed as parameter to the semop function */ +struct sembuf { + unsigned short sem_num; /* Semaphore number */ + short sem_op; /* Semaphore operation */ + short sem_flg; /* Operation flags */ +}; + +/* + * Semaphore info structure. Useful for the ipcs + * standard utily + */ +struct seminfo { + int semmni; /* Number of semaphore identifies */ + int semmns; /* Number of semaphore in system */ + int semmnu; /* Number of undo structures in system */ + int semmsl; /* Max number of semaphores per id */ + int semopm; /* Max number of operations per semop call */ + int semume; /* Max number of undo entries per process */ + int semusz; /* Size in bytes of undo structure */ + int semvmx; /* Semaphore maximum valure */ + int semaem; /* adjust on exit max value */ +}; + + +__BEGIN_DECLS + +int semctl(int sem_id, int sem_num, int command, ...); +int semget(key_t key, int num_sems, int sem_flags); +int semop(int sem_id, struct sembuf *sem_ops, size_t num_sem_ops); + +__END_DECLS + + +#endif /* _SYS_SEM_H */ Index: headers/private/kernel/posix/xsi_semaphore.h =================================================================== --- headers/private/kernel/posix/xsi_semaphore.h (revision 0) +++ headers/private/kernel/posix/xsi_semaphore.h (revision 0) @@ -0,0 +1,34 @@ +/* + * Copyright 2008, Haiku Inc. All rights reserved. + * Distributed under the terms of the MIT License. + */ +#ifndef KERNEL_XSI_H +#define KERNEL_XSI_H + +#include <sys/sem.h> +#include <sys/cdefs.h> + +#include <OS.h> + +#include <kernel.h> + +union semun { + int val; + struct semid_ds *buf; + unsigned short *array; +}; + +__BEGIN_DECLS + +extern void xsi_ipc_init(); +extern void xsi_do_undo(team_id teamID, short numberOfUndos); + +/* user calls */ +int _user_xsi_semget(key_t key, int numberOfSemaphores, int flags); +int _user_xsi_semctl(int semaphoreID, int semaphoreNumber, int command, + union semun* args); +status_t _user_xsi_semop(int semaphoreID, struct sembuf *sops, size_t nsops); + +__END_DECLS + +#endif /* KERNEL_XSI_H */ Index: headers/private/kernel/thread_types.h =================================================================== --- headers/private/kernel/thread_types.h (revision 26666) +++ headers/private/kernel/thread_types.h (working copy) @@ -49,6 +49,7 @@ JOB_CONTROL_STATE_DEAD } job_control_state; + // The type of object a thread blocks on (thread::wait::type, set by // thread_prepare_to_block()). enum { @@ -182,6 +183,7 @@ int32 flags; void *io_context; struct realtime_sem_context *realtime_sem_context; + short xsi_sem_undo_requests; sem_id death_sem; // semaphore to wait on for dying threads struct list dead_threads; int dead_threads_count;