Subject: How unique do instances of sctp_assoc_id need to be?

From: "La Monte H.P. Yarroll" <[email-masked]>
Date: Thu, 13 May 2004 09:24:45 -0400

This is a question about implementing the sockets API.

How unique do association identifiers need to be on a single 1-many
socket?

Do bad things happen if we use a first-fit algorithm for
picking new identifiers?  I.e. is it safe to reuse an association
identifier immediately after the association that had it before
shuts down?

The Linux kernel provides an identifier generating and tracking
subsystem which defaults to providing first-fit identifiers.  We
can force it to generate monotonicly increasing identifiers, but
memory efficiency drops significantly.  Is it worth paying the
memory price to get identifiers which recirculate less often?

My model application for thinking about this problem is a long-lived
telecomm app which creates a few control associations early on in life
and then creates a lot of shorter-lived bearer associations.  The
lifetimes of the bearer associations would probably have an exponential
distribution.

If first-fit is too agressive for recirculating identifiers, how large
a pool is large enough?  Looking at the existing code, it would not
be difficult to recirculate in a pool of 256 identifiers without
additional memory penalty...

-- 
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell's sig

---

From: "Randall Stewart (cisco)" <[email-masked]>
Date: Thu, 13 May 2004 13:52:33 -0400

La Monte:

I think Kacheong pointed this out a while back in
an authors-discussion of the sockets api...

Some language needs to be added to the draft in this
vein (if I remember K's comment right) that says apps
should be aware of reuse possiblity... did we do this.. hmm .. I will
have to check ...

Those that need to use the associd and track it somehow
need to watch those pesky little association ending notifications.. so
that they will not have an issue with sending a message to
the wrong association for instance...

Doing something like you propose below will definetly help... I know
in KAME we make NO attempt to do anything to keep re-use from
happening... in fact it WILL happen a lot...

I will have to think on this if I want to add something along
these lines... sigh.. more code if I do.. and as you point out the
overhead, depending on how little re-circulation you want), can get
quite big after a bit.

R

-- 
Randall R. Stewart
ITD - Transport Technologies
815-477-2127(o) or 815-342-5222(c)

---

From: Caitlin Bestler <[email-masked]>
Date: Thu, 13 May 2004 22:01:26 +0300

> memory price to get identifiers which recirculate less often?

You seem to be assuming that the cycle-length of the association
ID is directly proportionate to the amount of tracking data required.

One simple solution is to have an "index", which determines the
cycle length, and a "serial number" which is changed each
time an index is re-issued. The association id is then formed
from the combination (via any of numerous possible methods).
Given an association id you can quickly find the index, and
the control data. You then check the serial number to make
sure that if this is a stale association ID it is *very* stale.

It doesn't achieve the maximum cycle time for the number of
bits in the association ID, but it does allow storage to be
scaled to match the maximum number of association IDs
rather than the association ID re-use span.

---

From: "La Monte H.P. Yarroll" <[email-masked]>
Date: Thu, 13 May 2004 16:35:33 -0400

> ID is directly proportionate to the amount of tracking data required.

Only for the implementation I need to use.  More below...

> sure that if this is a stale association ID it is *very* stale.

Until yesterday the Linux kernel IDR mechanism did something
similar.  The other users of IDR prefer first-fit and don't really
care about id reuse.  The code is being removed as unnecessary
complexity.

The default behavior is to do first-fit which pessimizes reuse.

There IS a mechanism for asking "give me new a new ID
higher than x".  This mechanism uses slightly more than n log n bits
for n sparse active ids.  This could be a few 10's of Kb for a long-
lived very active socket, just to track id numbers.

I'm trying to decide how loudly to complain about the loss of
functionality.  How common a bug is reuse after close?  How
much pain should I go through to help programmers detect
this class of bug?

I have four options:

1. Live with first fit.

2. Use the higher-than mechanism and pay the memory price.

3. Complain bitterly that I NEED the counter mechanism.

4. Ask for something less aggressive than first-fit like next-fit.

---

From: Kacheong Poon <[email-masked]>
Date: Fri, 21 May 2004 16:39:36 -0700

> should be aware of reuse possiblity... did we do this.. hmm .. I will

It is already in the current -08 draft.  See section 3.1.

 > the wrong association for instance...

It can be worse than that as the notification receive and sending
can be in the wrong order.  So if the app is not careful, it can
send to the wrong association as it has not done the notification
receive.  The solution is to force the app to do a close.  See
section 3.1.

 > overhead, depending on how little re-circulation you want), can get

A life time only minimizes the probability.  Explicit close
solves the issue, except in the case of SCTP_AUTOCLOSE.  App
must be careful when using SCTP_AUTOCLOSE.

-- 

						K. Poon.
						[email-masked]

---

From: Kacheong Poon <[email-masked]>
Date: Fri, 21 May 2004 16:40:15 -0700

> rather than the association ID re-use span.

Yes, this was similar to one of the ideas to get around the
problem.  But we thought that the aid resue is really an
interface problem, not an implementation problem.  So to solve
it cleanly, it should be done in the interface.  This is the
same issue as a file descriptor, and we know how it is handled.

-- 

						K. Poon.
						[email-masked]

---

From: "La Monte H.P. Yarroll" <[email-masked]>
Date: Tue, 25 May 2004 09:36:54 -0400

> receive.  The solution is to force the app to do a close.  See

At least in Linux, we can tell if the app has done a
receive of the end notification.  Is this not true for
Solaris?  I know that Streams hides a lot of information
from the implementation...

> must be careful when using SCTP_AUTOCLOSE.

 From the perspective of the SCTP implementation, is it
sufficient to not reuse the identifier until the ending
notification is delivered?

Hmm... I can answer my own question--no.  An implementation
needs to keep the associd until all references to it are
gone, both in the upward bound queue of messages to the
app and in the downward bound queue of requests from the
app.

Is there a way that an app writer can know that they will
never see mention of a particular association again?  I'm
pretty sure the app can still get an error message about an
association even after it has received a SHUTDOWN COMPLETE
notification.