[haiku-gsoc] Re: XSI semaphore implamentation patch #2

On 2008-08-01 at 13:14:24 [+0200], Salvatore Benedetto <emitrax@xxxxxxxxx> 
wrote:
> 2008/7/30 Ingo Weinhold <ingo_weinhold@xxxxxx>:
> >
> > Managing too lists is not really more complex than managing one list and a
> > counter. You basically have to replace the counter increments/decrements 
> > by
> > list adds/removes. The only additional complexity is the per team 
> > structure,
> > but that is needed anyway to keep track of private semaphore sets, that
> > should be deleted on team exit/exec*().
> >
> > I would go with an undo entry per semaphore set and team, BTW.
> 
> Hmm...  Let's say I use the following structure, and you agree :-)
> 
> struct undoRequest : DoublyLinkedList<undoRequest> {
>      union {
>           team *team;  // Used in the sem list
>           XsiSemaphoreSet *semaphore_set; // Used in the team
>      } p;
>      short  undo_value;
>      int      semaphore_number;
> }

Nope, I don't agree. As I wrote, I would go with an entry per semaphore set 
and team:

struct UndoEntry : DoublyLinkedListLinkImpl<UndoEntry> {
        DoublyLinkedListLink<UndoEntry> team_link;
        XsiSemaphoreSet*                                semaphore_set;
        struct team*                                    team;
        int16                                                   undo_values[0];
};

The entry would be in both the semaphore set and the team list. For each 
semaphore in the set there is an "undo_values" array element.

> First of all, everytime there is an undo request you have to create two very
> same structure and add it to both list (team and sem set). But that could 
> be ok.

One has to create only one entry which is added to both lists (currently you 
create on entry and add it to the global list and have to increment the 
counter in the team). If the semaphore set does already have an entry for the 
team, merely the array element for the concerned semaphore needs to be 
adjusted.

> When either SETVAL/SETALL or RMID is called, you have to invalidate
> the undo_request of the team. Standard says to set to zero the undo_value 
> on SET
> call, but I'd say to just remove the request as in the RMID case.

In the SETVAL case, removing is not correct, since only one semaphore is 
affected. Iterating through the semaphore set's undo entry list and setting 
the respective array element to zero is the correct solution. And perfectly 
time-optimal.

In the SETALL case, removing would be possible, but memset()ing the arrays to 
0 is probably the better choice.

> So, 
> everytime
> the object is removed from the semaphore set list, the object of the
> same request
> has to be removed, or at least invalidate, from the team list and
> that's require to iterate through
> the list which can contain other semaphore set undo request (although you 
> could
> say that it contains less objects than the global undo list I use
> now). But still, you
> are required to iterated through two list to remove one request.

Removing from the other list is O(1), since it's the very same object. Just 
the same as decrementing the counter as in the current implementation.

> The reason the team request has to be removed is that, in worst case
> scenario, the semaphore
> set id, can be reused, and other sem_undo request can be added to it 
> meanwhile,
> so you won't know if the team undo request is still valid or not. Thus
> the need of removing
> it.

Not sure what you're aiming at, but yes RMID needs to remove all undo entries.

> Same thing happens, more or less, when the team exit. The semaphore
> set undo request
> must be removed, which requires to iterate through it's list (although
> the same observation
> of having less requests of the current global undo request can be applied).

And again, since the same undo entry object lives in both lists, the whole 
thing is O(n), with n being the number of semaphore sets the team has undo 
entries for, or IOW: optimal.

> >> 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.
> >
> > It doesn't make a difference when SETVAL/SETALL are called or whether 
> > there
> > are undo entries for these semaphores, since you unconditionally iterate
> > through the whole global undo entry list in any case.
> 
> Exactly. And that can be easily fixed with a counter in the set.

Yep, that can and probably should be done, if you don't implement my proposal.

That reminds me: You have a locking order inversion in xsi_sem_undo(): It's 
sUndoListLock -> sXsiSemaphoreSetLock, while it is the other way around in 
_user_xsi_sem{op,ctl}().

> Seriously, I understand your concern about perfomances and I don't mean
> in any way to waist your time, but I thought optimization in this situation
> could be postponed.

Yep, I'd much prefer unit tests first.

CU, Ingo

Other related posts: