Date: Mon, 16 Jun 2003 14:16:34 +1000 (EST) From: Bruce Evans <bde@zeta.org.au> To: Ian Dowse <iedowse@maths.tcd.ie> Cc: freebsd-arch@freebsd.org Subject: Re: Message buffer and printf reentrancy patch Message-ID: <20030616125941.G26874@gamplex.bde.org> In-Reply-To: <200306151956.aa86884@salmon.maths.tcd.ie> References: <200306151956.aa86884@salmon.maths.tcd.ie>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, 15 Jun 2003, Ian Dowse wrote: > In message <200306151826.h5FIPvM7046944@gw.catspoiler.org>, Don Lewis writes: > > > >> +#define MSGBUF_SEQNORM(mbp, seq) ((seq) % (mbp)->msg_seqmod + ((seq) < 0 ? > >\ > >> + (mbp)->msg_seqmod : 0)) > >> +#define MSGBUF_SEQ_TO_POS(mbp, seq) ((int)((u_int)(seq) % \ > >> + (u_int)(mbp)->msg_size)) > >> +#define MSGBUF_SEQSUB(mbp, seq1, seq2) (MSGBUF_SEQNORM(mbp, (seq1) - (seq2) > >)) > >> + Sorry I didn't reply to Ian's provate mail about all this last month. I'll try to get back to it. > >According to my copy of K&R, there is no guarantee that ((negative_int % > >postive_int) <= 0) on all platforms, though this is generally true. C99 guarantees this perfect brokenness of the % operator. Division should give remainders that have the same sign as the divisor, which corresponds to rounding towards minus infinity for positive divisors, but is now specified to be bug for bug compatible with most hardware and most C implementations (round towards zero). MSGBUF_SEQ_TO_POS() does extra work to get nonnegative remainders. This problem and many casts could be avoided by using unsigned types for most of the msgbuf fields. I forget the details of why we changed them back to signed. The log message for msgbuf.h 1.19 says that this is because we perform signed arithmetic on them. The details for this, can probably be handled by the macros now. > >If the sequence numbers wrap, there will be a discontinuity in the > >sequence of normalized sequence numbers unless msg_seqmod evenly divides > >the full integer range, which would indicate that msg_seqmod needs to be > >a power of two on the platforms of interest. > > > >Integer division is fairly slow operation for most CPUs, so why not just > >enforce the power of two constraint and just grab the bottom bits of the > >sequence numbers using a bitwise logical operation to normalize? > > The sequence number mechanism could do with a few further comments, > as it's not particularily obvious what is going on. As you point > out, a simple mapping from a binary sequence number to an index > using the modulo operation will suffer discontinuities when the > sequence numbers wrap, unless the size divides into the range of > the sequence numbers. > > The code here (unless I've missed something) deals with that by > ensuring that the range of the sequence numbers is always a multiple > of the message buffer size, and that's why the odd normalisation > macro is needed. The msg_seqmod field is initialised to 16 times > the message buffer size, so by using MSGBUF_SEQNORM() whenever the > sequence numbers are updated, there are no discontinuities in the > value of MSGBUF_SEQ_TO_POS() as the sequence numbers advance. By > using atomic_cmpset*, it can be guaranteed that sequence numbers > outside this range never make it to the pointers. The value 16 is > just chosen to make it quite unlikely for an old sequence number > to be interpreted as current. This seem correct but messy. > Bruce originally suggested this approach, and he suggested using a > power of 2 message buffer size so that a simple binary operation > could be performed in MSGBUF_SEQ_TO_POS(). The problem is that > MSGBUF_SIZE has been documented for a long time as only being > restricted to a multiple of the page size, and then the top few > bytes get taken by the msgbuf structure. This combined with the > fact that the message buffer is allocated in MD code would make it > waste memory (you'd always lose PAGE_SIZE - sizeof(struct msgbuf)), > messy to change, and would require many people to modify their > kernel configurations. I don't particularily like the divisions > either, but it seems very unlikely to me that they will be significant > in practice. I mainly suggested the power of 2 part. My original idea for the sequence numbers was interpret msg_bufx as a sequence number instead of as an index to fix the current races setting the index. The most serious race is resetting the index to 0 and this goes away with sequence numbers since sequence numbers can grow without bounds (actually to to the limit of the data type, which is almost enough for anyone with 32-bit ints). The details are messier in practice :-]. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030616125941.G26874>