[haiku-gsoc] Re: Xsi semaphorses: patch #1
- From: Ingo Weinhold <ingo_weinhold@xxxxxx>
- To: haiku-gsoc@xxxxxxxxxxxxx
- Date: Mon, 14 Jul 2008 15:31:23 +0200
On 2008-07-14 at 12:48:08 [+0200], Salvatore Benedetto <emitrax@xxxxxxxxx>
wrote:
> >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?
I don't know what bonnie++ is doing, but I guess it uses semaphore for some
kind of synchronization. Why would that be a good test for the semaphore
implementation? Probably the only thing that will happen is that the
multi-threaded tests will fail sometimes and it will be hard to tell why.
> > 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.
I don't remember having read this on this list. Anyway, I'm fine with a
partial XSI semaphores implementation as long as it isn't committed to the
trunk, since this will potentially add problems to ports that use them.
> 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.
It's not that complicated. The basic idea is that for each team the changes
to each semaphore need to be summed up. When the team exits the changes need
to be reverted.
> > +// 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.
Maybe. When blocking fails (due to interrupt) the thread needs to dequeue
itself. Unless you use the thread spinlock for protecting the queues there
will be a race condition during which another thread could dequeue the
thread. This is where "queued" would be used.
> > +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.
Spinlocks are just another (more low level) means of synchronization. Their
main advantage is that they can be used with interrupts disabled.
Disadvantages are that one has to disable interrupts to use them, which makes
them unfit for longer critical sections, and that they waste real CPU time
for high lock contention (on SMP systems only, of course). Generally mutexes
should be preferred, if they can be used.
> > + 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.
Mmh well, at least you used it for the other hash table.
> 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 :-)
The returned hash value is not directly used as index. The hash table applies
a modulo first.
> > + 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.
One obvious point of using different tables is right here: It avoids special
cases. Another is that, since the standard is not very explicit in this
respect, I expect most programs not to share IPC keys for the different kinds
of IPC subsystems. So you would end up with table entries that potentially
reference three kinds of IPC objects, but actually reference only one.
> > + 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.
Yep, some kind of limit is needed. The number you're checking is just not
team related.
> > + 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.
OK, I guess this makes sense. In doubt check how other systems handle it.
[...]
> > 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).
If other systems implement it like this, I guess it is safe to do it this
way, too. The implementation I had in mind would queue the thread at all
semaphores which it would potentially have to wait for and only unblock it
when all conditions are fulfilled.
> > +
> > +// Semaphore operation flags
> > +#define SEM_UNDO 10
> >
> > Use C-style comments in public POSIX headers.
>
> We should agree on a single way for comments.
We do prefer C++-style comments. For ANSI compatibility we need to stick to
C-style comments in our public POSIX headers, though.
> > 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.
It's not, if Foo derives from HashTableLink<Foo>.
CU, Ingo
Other related posts:
