[haiku-gsoc] Re: Xsi semaphorses: patch #1
- From: "Salvatore Benedetto" <emitrax@xxxxxxxxx>
- To: haiku-gsoc@xxxxxxxxxxxxx
- Date: Mon, 14 Jul 2008 10:48:08 +0000
>2008/7/13 Ingo Weinhold <ingo_weinhold@xxxxxx>
> Please do at least write some tests (e.g. cf.
> src/tests/system/libroot/posix/realtime_sem_test1.cpp for how this could
> look like). There might also be tests in the POSIX test suite.
I was going too (I still am) but I thuoght what better test than
bonnie++ itself?
>
> And please complete the XSI semaphores implementation before actually
> looking into bonnie++. E.g. APR favors XSI semaphores over realtime
> semaphores, because the former have the SEM_UNDO feature.
I talked to Axel and he agreed on adding the feature needed by bonnie++ first,
so I could start running test as I don't know how time consuming are they, and
meanwhile completing the implementation.
As for the SEM_UNDO feature, it hasn't been yet added because honestly I haven't
understand it yet, but I'll look more into it.
> +// 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;
> + bool destroyed;
> +};
>
> "destroyed" is not needed.
Yep, and probably not even "queued". I added the blocking part at the
end and I might rework it
a bit.
> + ~XsiSemaphore()
> + {
> + // For some reason the semaphore is getting destroyed.
> + // Wake up any remaing awaiting threads
> + GRAB_THREAD_LOCK();
>
> You need to disable interrupts before trying to acquire a spinlock. That's
> not done anywhere in the code.
Yes. Spinlock are actually missing (beside the thread one). I was supposed
to do add them before sending in the patch but as you can see I forgot about it.
> + // We return true in case the operation causes the
> + // caller to wait, so it can undo all the operations
> + // previously done, by calling the same function
> + // with force set to true, which causes the operation
> + // to take place despite the result of the algebric sum
> + bool Add(short value, bool force)
> + {
> + if (!force) {
> + if ((int)(fValue + value) < 0) {
> + TRACE(("XsiSemaphore::Add: going to
> sleep\n"));
> + return true;
> + } else {
> + fValue += value;
> + if ((fValue == 0) &&
> (fProcessesWaitingToBeZero > 0))
> + WakeUpThread(true);
> + else if ((fValue > 0) &&
> (fProcessesWaitingToIncrease > 0))
> + WakeUpThread(false);
> + return false;
> + }
> + }
> + // We are being forced to revert our changes
> + fValue -= value;
> + return false;
> + }
>
> This method should be split up in two. ATM, depending on "force" two
> completely different things (that share no common code at all) happen.
I wanted to try and reuse the code, but if you say so I have not
problem in splitting the method.
> +
> + pid_t GetPid() const
> + {
> + return fLastPidOperation;
> + }
>
> Coding style: Getters generally don't have a "Get" prefix, only when the
> method name would otherwise clash with a type name.
Unlike the other coding style erros, I totally forgot about this one.
I'll fix all of them.
> + status_t Wait(int32 count, bool waitForZero)
> + {
> + // 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);
> + fProcessesWaitingToBeZero++;
> + } else {
> + fWaitingToIncreaseQueue.Add(&queueEntry);
> + fProcessesWaitingToIncrease++;
> + }
> + queueEntry.queued = true;
> +
> + thread_prepare_to_block(thread, 0, THREAD_BLOCK_TYPE_OTHER,
> + (void*)"xsi semaphore");
> + GRAB_THREAD_LOCK();
> + status_t result = thread_block_locked(thread);
>
> Waiting must be interruptable! Pass B_CAN_INTERRUPT to
> thread_prepare_to_block().
Ok.
> + void WakeUpThread(bool waitingForZero)
> + {
> + queued_thread *entry;
> + bool unblock = false;
> +
> + GRAB_THREAD_LOCK();
> + if (waitingForZero) {
> + unblock = true;
> + entry = fWaitingToBeZeroQueue.RemoveHead();
> + } else {
> + entry = fWaitingToIncreaseQueue.Head();
> + if ((entry->count + fValue) > 0) {
> + unblock = true;
> + entry = fWaitingToIncreaseQueue.RemoveHead();
> + }
> + }
> + if (unblock) {
> + entry->queued = false;
> + entry->destroyed = true;
> + thread_unblock_locked(entry->thread, 0);
> + }
> + RELEASE_THREAD_LOCK();
> + }
>
> This method only unblocks one thread. In the "wait for zero" case other
> threads will be stuck.
Unless I'm missing a typo or something, threads waiting for the
semaphore to increase
will only be unblock if the operations they are about to do will
result greater than zero
(actually it should be equal or greater than zero).
> +private:
> + 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
> + Vector<XsiSemaphore*> fSemaphores;
>
> Why not just use a XsiSemaphore[]? Unless I miss something the number of
> semaphores never changes after having been created.
Actually they don't. The spec doens't say anything about adding or
removing single sempahore.
> +
> +static OpenHashTable<SemaphoreHashTableDefinition> sSemaphoreHashTable;
> +static int sNextAvailableID = 0;
> +static spinlock xsi_semaphore_set_spinlock = B_SPINLOCK_INITIALIZER;
> +#define GRAB_SEM_LOCK()
> acquire_spinlock(&xsi_semaphore_set_spinlock)
> +#define RELEASE_SEM_LOCK()
> release_spinlock(&xsi_sempahore_set_spinlock)
>
> Any particular reason for using a spinlock instead of a mutex? Besides the
> lock is not even used. In fact the complete implementation is totally
> lacking locking.
As I said above, I am fully aware of that.
As for the spinlock instead of a mutex I am probably missing something,
as I thought spinlocks are used for multiprocessor system while mutex are not.
> +
> + size_t HashKey (const key_t key) const
> + {
> + // TODO: Define a better hash function
> + // key_t is a 32 bit integer value.
> + return (size_t)(key & 0x00000fff) % 32;
>
> How about the obvious: "return (size_t)key"?
Because it's not obvious to me. I didn't look closely to
the OpenHashTable implementation, but I thought that the returned
value by HashKey is used as index in the hash table and the key itself
is a pretty big value. I'll have a closer look at it, but if someone in the
meantime want to shine some light for me on this one I wouldn't mind :-)
> +static OpenHashTable<IpcHashTableDefinition> sIpcHashTable;
> +static spinlock ipc_spinlock = B_SPINLOCK_INITIALIZER;
> +#define GRAB_IPC_TABLE_LOCK()
> acquire_spinlock(&ipc_spinlock);
> +#define RELEASE_IPC_TABLE_LOCK()
> release_spinlock(&ipc_spinlock);
>
> Same here: Why a spinlock?
Same as above. I'm defintely missing something.
>
>
> +
> +
> +status_t
> +haiku_xsi_ipc_init(struct kernel_args *args)
> +{
> + // Initialize hash tables
> + status_t error = sIpcHashTable.Init();
> + if (error != B_OK)
> + return error;
> + return sSemaphoreHashTable.Init();
> +}
>
> This function is never called. I suppose you want to do that in main.cpp.
Yes, this function is supposed to go there.
> +
> +int
> +_user_xsi_semget(key_t key, int numberOfSemaphores, int flags)
> +{
> + XsiSemaphoreSet *semaphoreSet = NULL;
> + Ipc *IpcKey = NULL;
>
> Coding style: ipcKey.
Typo. ;-)
> + if (key != IPC_PRIVATE) {
> + isPrivate = false;
> + // Check if key already have 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->GetSemaphoreSetID();
> + semaphoreSet =
> sSemaphoreHashTable.Lookup(semaphoreSetID);
> + if (!semaphoreSet->HasPermission()) {
> + TRACE_ERROR(("xsi_semget: calling process has
> not permission "
> + "on semaphore %d, key %d\n",
> semaphoreSet->GetID(),
> + (int)semaphoreSet->GetIpcKey()));
> + return EACCES;
> + }
> + if ((semaphoreSet->GetNumberOfSemaphores() <
> numberOfSemaphores)
> + && (numberOfSemaphores != 0)) {
> + TRACE_ERROR(("xsi_semget: nsems greater than
> the one "
> + "associated with semaphore %d, key
> %d\n",
> + semaphoreSet->GetID(),
> (int)semaphoreSet->GetIpcKey()));
> + return EINVAL;
> + }
> + create = false;
> + } else {
>
> I don't see this case happening, if one employs proper locking. I.e.
> creation of the semaphore and entering it into the table would be atomic.
It actually can happen if you considere the IPC table to be share
among shared memories
and message queues. You can have the same IPC for the message queues
and shared memory,
in fact I just checked that on my linux box and the same key (you can
use the ipcs command)
is used for shared memory and semaphore. The standard posix is not
really clear about this.
I plan to move the IPC code to its own source file and extend its
usage for message queues
and shared memory. I know we already talked about it and decided to
use 3 different tables
but I don't really see the point of that, besides other OSes don't
seems to do so.
> + if (create) {
> + // Create a new sempahore for this key
> + if (numberOfSemaphores < 0
> + || numberOfSemaphores >
> MAX_POSIX_SEMS_PER_TEAM) {
> + TRACE_ERROR(("xsi_semget: nsems out of
> range\n"));
> + return EINVAL;
> + }
>
> MAX_POSIX_SEMS_PER_TEAM is really not related.
Some kind of limit should obviusly be used and ATM I thought that
MAX_POSIX_SEMS_PER_TEAM would be fine.
>
> + if (sTotalNumberOfXsiSemaphores < MAX_XSI_SEMAPHORE) {
> + TRACE_ERROR(("xsi_semget: reached limit of
> maximum number of "
> + "semaphores
> allowed\n"));
> + return ENOSPC;
> + }
> + sTotalNumberOfXsiSemaphores++;
>
> Should be "if (sTotalNumberOfXsiSemaphores >= MAX_XSI_SEMAPHORE) {".
And typo again it is! ;-)
>
> + semaphoreSet = new(std::nothrow)
> XsiSemaphoreSet(numberOfSemaphores,flags);
>
> Coding style: Missing space after ",". 80 columns limit.
On my defense, the other day I dropped half of litre of iced tea with sugar
on my laptop while coding and thank God the computer is still up and running
but all keys became VERY sticky and typing has become harder!
> + if (semaphoreSet == NULL) {
> + TRACE_ERROR(("xsi_semget: failed to allocate
> a new xsi "
> + "semaphore set\n"));
> + sTotalNumberOfXsiSemaphores--;
> + return ENOMEM;
> + }
> + if (isPrivate)
> + semaphoreSet->SetIpcKey((key_t)-1);
> + else {
> + semaphoreSet->SetIpcKey(key);
> + IpcKey->SetSemaphoreSetID(semaphoreSet);
> + }
>
> Entering the semaphore into sSemaphoreHashTable is missing. I suppose you
> meant it to happen in XsiSemaphoreSet::SetID().
Not it was supposed to happen outside SetID().
>
>
> + }
> + }
> +
> + return semaphoreSet->GetID();
>
> The whole "if (create) {...}" block needs to be pulled out of the "if (key
> != IPC_PRIVATE) {...}". Otherwise we can't create private semaphores (and
> actually segfault at this point).
Ups...
> + if ((args != 0) && !(IS_USER_ADDRESS(args))) {
>
> Coding style: Superfluous parentheses (in both expressions). Encountered
> several times throughout the sources.
I thought they wouldn't hurt. I'll remove them.
> + int value;
> + user_memcpy(&value, &args->val, sizeof(int));
>
> The return value of user_memcpy() must be checked!
True!
> + if (value > USHRT_MAX) {
> + TRACE_ERROR(("xsi_semctl: value %d out of
> range\n", value));
> + return ERANGE;
> + }
> + semaphore->SetValue(value);
>
> I suppose this should potentially unblock threads.
Honesly, I'm not sure, but I think it shouldn't. SetValue is supposed
to initiliaze the sempahore,
so technically no other thread before this would have used the semaphore.
> + return 0;
> +
> + case GETPID:
> + if (!(semaphoreSet->HasReadPermission())) {
> + TRACE_ERROR(("xsi_semctl: calling process has not
> permission "
> + "on semaphore %d, key %d\n",
> semaphoreSet->GetID(),
> + (int)semaphoreSet->GetIpcKey()));
> + return EACCES;
> + }
>
> Indentation.
Copy&Paste issues.
> + case IPC_STAT:
> + case IPC_SET:
> + // TODO
>
> If something is not implemented, it should fail, not do something totally
> unexpected (like destroying the semaphore set when a stat was requested).
Yes, return -1 missing.
> + case IPC_RMID:
> + if (!(semaphoreSet->HasPermission())) {
> + TRACE_ERROR(("xsi_semctl: calling
> process has not permission "
> + "on semaphore %d, key %d\n",
> semaphoreSet->GetID(),
> +
> (int)semaphoreSet->GetIpcKey()));
> + return EACCES;
> + }
> + sSemaphoreHashTable.Remove(semaphoreSet);
> + delete semaphoreSet;
> +
> +
>
> Should also remove the IPC key from sIpcHashTable.
Definitely!
> Coding style: Superfluous spacing.
I'll look closer, as I don't see it right now.
> + int i = 0;
> + for (; i < nsops; i++) {
> + short semaphoreNumber = operations[i].sem_num;
> + if (semaphoreNumber > numberOfSemaphores) {
>
> Should be >=.
True.
> + unsigned short value = semaphore->GetValue();
> + short operation = operations[i].sem_op;
> + if (operation < 0) {
> + if (semaphore->Add(operation, false)) {
> + 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, false);
> + }
> + }
> +
> + // Either we have to wait or an error occured
> + if (goToSleep || result != 0) {
> + // Undo all previosly done operations
> + for (int j = 0; j < i; j++) {
> + short semaphoreNumber = operations[j].sem_num;
> + semaphore =
> semaphoreSet->GetSemaphore(semaphoreNumber);
> + short operation = operations[j].sem_op;
> + if (operation != 0)
> + semaphore->Add(operation, true);
> + }
> + if (result != 0)
> + return result;
> +
> + bool waitOnZero = true;
> + if (operations[i].sem_op != 0)
> + waitOnZero = false;
> +
> + result = semaphore->Wait((int32)operations[i].sem_op,
> waitOnZero);
> +
> + // We are back to life.
> + // Find out why!
> + semaphoreSet =
> sSemaphoreHashTable.Lookup(semaphoreID);
> + if (semaphoreSet == NULL || result == EIDRM) {
> + TRACE_ERROR(("xsi_semop: semaphore set id %d
> got destroyed\n",
> + semaphoreID));
> + result = EIDRM;
> + notDone = false;
> + }
> + } else
> + // everything worked like a charm
> + notDone = false;
> + // TODO: Handle SEM_UNDO requests
> + }
> + return result;
> +}
>
> I'm not sure, if this implementation works as it is supposed to work. It
> only waits for one semaphore at a time. Thus at least the semncnt and
> semzcnt won't be correct when it actually would wait for more than one
> semaphore.
I was heavily "inspired" by the openbsd implementation on this one.
I don't see why you would wait on more then one semaphore, even if you
are waiting on two semaphore, and gets awaken on one of the
two, you still have to wait for the other one, while holding a "virtual" lock
on the other semaphore which my cause a deadlock (by virtual lock I mean
you might have changed the value of the semaphore and it keeps another thread
from using it).
>
> Please use the the macro defined in headers/private/shared/syscall_utils.h.
> Particularly note that your version instantiates the argument three times
> and evaluates it least twice, which makes the code below incorrect.
At first I actually use that one, but the C file failed to compile due
to a syntax error
which made me waste a whole afternoon and I only fixed it thanks to Renè!
Personally I don't really know why, but it has something do to with
the raseResult
value being resulting defined in the middle of the function.
> Index: headers/posix/sys/types.h
> ===================================================================
> --- headers/posix/sys/types.h (revision 26404)
> +++ headers/posix/sys/types.h (working copy)
> @@ -1,5 +1,6 @@
> /*
> - * Distributed under the terms of the OpenBeOS license
> + * Copyright 2008, Haiku Inc. All Rights Reserved.
> + * Distributed under the terms of the MIT License.
> */
> #ifndef _SYS_TYPES_H
> #define _SYS_TYPES_H
>
> This is a totally unrelated change.
You think? :-)
> +
> +// Semaphore operation flags
> +#define SEM_UNDO 10
>
> Use C-style comments in public POSIX headers.
We should agree on a single way for comments.
> Index: headers/private/kernel/util/OpenHashTable.h
> ===================================================================
> --- headers/private/kernel/util/OpenHashTable.h (revision 26404)
> +++ headers/private/kernel/util/OpenHashTable.h (working copy)
> @@ -30,7 +30,7 @@
> size_t HashKey(int key) const { return key >> 1; }
> size_t Hash(Foo *value) const { return HashKey(value->bar); }
> bool Compare(int key, Foo *value) const { return value->bar ==
> key; }
> - HashTableLink<Foo> *GetLink(Foo *value) const { return value;
> }
> + HashTableLink<Foo> *GetLink(Foo *value) const { return
> &value->otherLink;
> }
> };
> */
>
> Unrelated, and not even something that needs changing.
Totally OT, but on that matter I thought the comment was actually wrong
as the return type is different.
> struct user_disk_device_job_info;
> struct user_disk_system_info;
>
> +union semun;
> // This marks the beginning of the syscalls prototypes for gensyscallinfos.
> // NOTE:
> // * Nothing but those prototypes may live here.
>
> Spacing: the "union semun;" declaration really has nothing to do with the
> following comment lines. Besides, I would simply also put it into the list
> above.
I only forgot to add a blank line before the comments. It is supposed to
be part of that list about but being the only union I thought to add also
a blank line after the list of structs.
Thanks a lot for looking through my patch!
Regards,
--
Salvatore Benedetto (a.k.a. emitrax)
Student of Computer Engineer
University of Pisa
www.haiku-os.it
Other related posts:
