Date: Sun, 15 Jun 2003 19:56:58 +0100 From: Ian Dowse <iedowse@maths.tcd.ie> To: Don Lewis <truckman@FreeBSD.org> Cc: freebsd-arch@FreeBSD.org Subject: Re: Message buffer and printf reentrancy patch Message-ID: <200306151956.aa86884@salmon.maths.tcd.ie> In-Reply-To: Your message of "Sun, 15 Jun 2003 11:25:57 PDT." <200306151826.h5FIPvM7046944@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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) >)) >> + > >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. > >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. 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. Ian
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200306151956.aa86884>