Date: Wed, 20 Dec 2000 14:09:31 -0800 From: Julian Elischer <julian@elischer.org> To: James Mansion <james@westongold.com> Cc: Chuck Paterson <cp@bsdi.com>, smp@FreeBSD.ORG Subject: Re: Netgraph locking primatives. take 1. Message-ID: <3A412E1B.9BB52D59@elischer.org> References: <ODEEJFFGLIBKGLFBJHOIEEBHDCAA.james@westongold.com>
next in thread | previous in thread | raw e-mail | index | archive | help
James Mansion wrote:
>
> >Threads never hold more than one of these locks.
> >either you are running in node X in which case you hold a reader
> >lock on Node X or you are running in node Y in which you hold a
> >reader lock on node Y. the same message cannot be delivered
>
> How so?
>
> Do you never MOVE from X to Y?
>
> If you do so by:
> - establish location of Y
> - release X
> - acquire Y
>
> Then there is a race with the destruction of Y. And if you
> go:
> - establish location of Y
> - acquire Y
> - release Y
> then you can deadlock.
You can't deadlock because the action on failing to get a lock
is to queue the item for later delivery to Y and then leave.
Whoever presently has Y is required to process the request when they
are finished with whatever they are presently doing.
(and they already HAVE the lock).
If they decide to destroy the node then part of that is to flush the queue.
>
> Is it really worh acquiring locks at a node level - surely
> if most of the time you are not changing the node structure,
> then it would be easier and (if you touch multiple nodes)
> much cheaper to acquire read/write on the whole structure?
this is exactly teh problem I'm struggling with now...
but:
the average netgraph traversal is through only 2 or 3 nodes.
which requires getting 3 locks.
getting nondestructive locks is only 4 machine instructions
which includes an atomic add to memory (in the case
of non collision) and another 3 instructions (with an atomic
subtract) on exit.
so on the easy case thats only about 6 atomic bus cycles
(which is the major cost) vs 2 for gaining and dropping
a global lock on netgraph. However using a global lock
on netgraph makes node deletion a little simpler as I can
guarantee that no-one is doing node lookups while I futz with the
node lists. Against that a global lock may require more
instructions and is more likely to have a colission, and
therefore less likely to use the otimised quick path..
(it goes from 4 instructions to about 50 for the unoptimised
path.)
As well, on a machine rnning many virtual channels on
(say) a T3, there would be many netgraph paths. and locking
the entire tree every time I wanted to bring up or down a circuit
could be interfering with many hundreds of circuits.
It would be better to only lock 1 node in that case.
>
> James
>
> To Unsubscribe: send mail to majordomo@FreeBSD.org
> with "unsubscribe freebsd-smp" in the body of the message
--
__--_|\ Julian Elischer
/ \ julian@elischer.org
( OZ ) World tour 2000
---> X_.---._/ presently in: Budapest
v
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-smp" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3A412E1B.9BB52D59>