fanf: (dotat)
[personal profile] fanf

There was an interesting and instructive cockup in the BIND 9.10.4 release. The tl;dr is that they tried to improve performance by changing the layout of a data structure to use less memory. As a side effect, two separate sets of flags ended up packed into the same word. Unfortunately, these different sets of flags were protected by different locks. This overlap meant that concurrent access to one set of flags could interfere with access to the other set of flags. This led to a violation of BIND's self-consistency checks, causing a crash.

The fix uses an obscure feature of C structure bitfield syntax. If you declare a bitfield without a name and with a zero width (in this case, unsigned int :0) any following bitfields must be placed in the next "storage unit". This is described in the C standard section

You can see this in action in the BIND DNS red-black tree declaration.

A :0 solves the problem, right?

So a clever idea might be to use this :0 bitfield separator so that the different sets of bitfields will be allocated in different words, and the different words will be protected by different locks.

What are the assumptions behind this fix?

If you only use a :0 separator, you are assuming that a "word" (in a vague hand-wavey sense) corresponds to both a "storage unit", which the compiler uses for struct layouts, and also to the size of memory access the CPU uses for bitfields, which matters when we are using locks to keep some accesses separate from each other.

What is a storage unit?

The C standard specifies the representation of bitfields in section

Values stored in bit-fields consist of m bits, where m is the size specified for the bit-field. The object representation is the set of m bits the bit-field comprises in the addressable storage unit holding it.

Annex J, which covers portability issues, says:

The following are unspecified: [... yada yada ...]

The alignment of the addressable storage unit allocated to hold a bit-field

What is a storage unit really?

A "storage unit" is defined by the platform's ABI, which for BIND usually means the System V Application Binary Interface. The amd64 version covers bit fields in section 3.1.2. It says,

  • bit-fields must be contained in a storage unit appropriate for its declared type

  • bit-fields may share a storage unit with other struct / union members

In this particular case, the storage unit is 4 bytes for a 32 bit unsigned int. Note that this is less than the architecture's nominal 64 bit width.

How does a storage unit correspond to memory access widths?

Who knows?


It is unspecified.


The broken code declared a bunch of adjacent bit fields and forgot that they were accessed under different locks.

Now, you might hope that you could just add a :0 to split these bitfields into separate storage units, and the split would be enough to also separate the CPU's memory accesses to the different storage units.

But you would be assuming that the code that accesses the bitfields will be compiled to use unsigned int sized memory accesses to read and write the unsigned int sized storage units.

Um, do we have any guarantees about access size?

Yes! There is sig_atomic_t which has been around since C89, and a load of very recent atomic stuff. But none of it is used by this part of BIND's code.

(Also, worryingly, the AMD64 SVABI does not mention "atomic".)

So what is this "Deathstation 9000" thing then?

The DS9K is the canonical epithet for the most awkward possible implementation of C, which follows the standard to the letter, but also violates common assumptions about how C works in practice. It is invoked as a horrible nightmare, but in recent years it has become a disastrous reality as compilers have started exploiting undefined behaviour to support advanced optimizations.

(Sadly the Armed Response Technologies website has died, and Wikipedia's DS9K page has been deleted. About the only place you can find information about it is in old comp.lang.c posts...)

And why is the DS9K relevant?

Well, in this case we don't need to go deep into DS9K territory. There are vaguely reasonable ABIs for which a small :0 fix would not actually work.

For instance, there might be a CPU which can only do 64 bit memory accesses, but which has a 32 bit int storage unit. This type representation would probably mean the C compiler has really bad performance, so it is fairly unlikely. But it is allowed, and there are (or were) CPUs which can't do sub-word memory accesses, and which have very little RAM so they want to pack data tightly.

On a CPU like this, the storage unit doesn't match the memory access, so C's :0 syntax for skipping to the next storage unit will fail to achieve the desired effect of isolating memory accesses that have to be performed under different concurrent access locks.

DS9K defence technology

So the BIND 9.10.4 fix does two things:

The most important change is to move one of the sets of bitfields from the start of the struct to the end of it. This means there are several pointers in between the fields protected by one lock and the fields protected by the other lock, so even a DS9K can't reasonably muddle them up.

Secondly, they used magical :0 syntax and extensive comments to (hopefully) prevent the erroneous compaction from happening again. Even if the bitfields get moved back to the start of the struct (so the pointers no longer provide insulation) the :0 might help to prevent the bug from causing crashes.

(edited to add)

When I wrapped this article up originally, I forgot to return to sig_atomic_t. If, as a third fix, these bitfields were also changed from unsigned int to sig_atomic_t, it would further help to avoid problems on systems where the natural atomic access width is wider than an int, like the lesser cousin of the DS9K I outlined above. However, sig_atomic_t can be signed or unsigned so it adds a new portability wrinkle.


The clever :0 is not enough, and the BIND developers were right not to rely on it.

Date: 2016-05-20 05:02 am (UTC)
ext_8103: (Default)
From: [identity profile]
C99 tells us almost nothing about 'storage units' - pretty much just that they are 'addressable'. No alignment restrictions, no requirement that they're all the same size, no requirement that each bitfield is contained in exactly one storage unit, no explicit prohibition on sharing them with non-bitfields. We can see that they can be adjacent to one another or in a 'next' relationship but that doesn't explicitly rule out gaps between them.
As such I think an implementation could state that the storage units of a given struct are bounded only by its endpoints and any :0 bit-fields. Yuck.

Date: 2016-05-20 08:46 am (UTC)
gerald_duck: (sideon)
From: [personal profile] gerald_duck
Even sig_atomic_t is helpless in the face of multi-threading. Until comparatively recently, the C++ standard was entirely silent on how two threads manipulating the same memory would interact. C++11 started talking about it, and I assume recent C standards do, too?

But I'll bet Bind expects to compile and run on older compilers, too!

Multi-threading is an intensely subtle and perilous field. Getting it right keeps me in good money.

Date: 2016-05-21 05:38 pm (UTC)
From: [identity profile]
The machine-specific atomics implementations are an optional optimization. (Heck, even threading is still an optional optimization in BIND.) I think it falls back to a generic implementation if you're on a platform they haven't ported it to. Personally, I think they're more trouble than they're worth -- see, e.g., -- and ought to be replaced with calls to the equivalent machine-independent compiler-provided intrinsics, on compilers that support those intrinsics.

I'm not sure if ISC has a formally defined portability target for BIND (at least, I don't think they did when I was there). But you'll occasionally see commits targeting systems that have long since been abandoned by their vendors, e.g.:;a=commitdiff;h=6f6b1abb106d970f1b0c5e959cddfabc9cc3b4ae

Date: 2016-05-22 03:15 am (UTC)
mr_cellaneous: (me)
From: [personal profile] mr_cellaneous
BIND's portability target when it was originally written was C90 and POSIX.1, but there has unavoidably been some drift, as we can't test everywhere.

The practical answer is, if there's a portability problem on any current Linux, any current BSD, MacOSX, Solaris, or Windows 2008 and higher, we'll be in a position to notice and fix it.

Date: 2016-05-20 09:37 am (UTC)
From: [identity profile]
How have I not read about DS9K before? That's a perfect description of what architecture you aim for (or preferably not aim for).

Is there a requirement that DS9K endianness is consistent...?


Date: 2017-01-11 09:55 am (UTC)
From: (Anonymous)

[url=]comprar viagra[/url]
[url=]levitra original[/url]
[url=]viagra sin receta[/url]
[url=]levitra sin receta[/url]
[url=]levitra sin receta[/url]


Date: 2017-01-26 07:14 pm (UTC)
From: (Anonymous)

[url=]Negozio Reebok Brescia[/url]
[url=]Air Max Thea Beige Clair[/url]
[url=]Cappello Jordan Invernale[/url]
[url=]Adidas Superstar Noir Et Blanc Femme[/url]
[url=]Air Jordan Grise Foot Locker[/url]


Date: 2017-02-11 05:37 am (UTC)
From: (Anonymous)

[url=]Reebok Azul Rey[/url]
[url=]Nike Thea Womens Puestas[/url]
[url=]Nike Roshe Run Swag[/url]
[url=]Air Max One Rojas[/url]
[url=]New York Gorras[/url]


Date: 2017-02-22 09:03 am (UTC)
From: (Anonymous)

[url=]Puma Suede Bordeaux[/url]
[url=]Ray Ban Polarized[/url]
[url=]Nike Air Max Thea Wit Grijs[/url]
[url=]Puma Suede Platform Tumblr[/url]
[url=]Huarache Wit[/url]


Date: 2017-02-23 05:02 am (UTC)
From: (Anonymous)

[url=]Oakley Radarlock 2016[/url]
[url=]Air Max 1 Essential[/url]
[url=]Donde Comprar Calzado Mbt Barato[/url]
[url=]Nike Azul Turquesa[/url]
[url=]Vans Chukka Low[/url]


Date: 2017-02-23 12:34 pm (UTC)
From: (Anonymous)

[url=]Reebok Crossfit Lifter Sverige[/url]
[url=]Adidas Primeknit Schuhe[/url]
[url=]Asics Dynaflyte Cena[/url]
[url=]Nike Hyperdunk Low[/url]
[url=]Vita Puma Skor[/url]


Date: 2017-03-14 02:16 pm (UTC)
From: (Anonymous)

[url=]Puma Velvet Creepers Burgundy Velvet Fenty[/url]
[url=]Puma Shoes Price List With Picture[/url]
[url=]Scarpe Puma Nuove Femminili[/url]
[url=]Puma Creepers Rihanna Burgundy[/url]
[url=]Puma Schuhe[/url]
From: (Anonymous)
Do you feel the pain of acid reflux? Do you feel a fire inside your chest? Are you miserable? Are you ready for the issues to stop? Continue reading to find out how. Keep reading to learn to control acid reflux for good and to end the misery for good.

You may need to balance out hydrochloric acid amounts in your body if you want to reduce acid reflux and its symptoms. You can do this, for instance, by using sea salt rather than table salt. Sea salt has chloride and minerals that are good for the stomach and prevent acid.



Date: 2017-03-16 04:01 pm (UTC)
From: (Anonymous)

[url=]Nike Air Max 1 Essential Navy[/url]
[url=]Air Max 1 Kumquat[/url]
[url=]Nike Air Max Zero Qs On Feet[/url]
[url=]Adidas Nmd Grise[/url]
[url=]Air Max Black Gum Sole[/url]


Date: 2017-03-17 03:37 am (UTC)
From: (Anonymous)

[url=]Chaussures Hogan Homme Occasion[/url]
[url=]Chaussures Lacoste Light 2.0[/url]
[url=]Le Coq Sportif Titanium[/url]
[url=]Le Coq Sportif Noir Femme[/url]
[url=]Le Coq Sportif Dynacomf Glitter[/url]


Date: 2017-03-17 03:53 am (UTC)
From: (Anonymous)

[url=]Air Max 95 Black And Blue Jd[/url]
[url=]Air Max Thea Joli[/url]
[url=]Air Max Thea Grise Et Rose Pas Cher[/url]
[url=]Basket Nike Bleu Turquoise[/url]
[url=]Air Max Thea Noire Femme[/url]


Date: 2017-03-17 11:16 pm (UTC)
From: (Anonymous)

[url=]Air Force One Rouge Basse[/url]
[url=]Lunettes Soleil Ray Ban Femme[/url]
[url=]Lunettes De Vue Ray Ban[/url]
[url=]Huarache Run Ultra Femme[/url]
[url=]Lunette De Soleil Oakley Homme 2016[/url]


Date: 2017-03-20 04:04 pm (UTC)
From: (Anonymous)

[url=]Asics Crossover 5 Dames[/url]
[url=]Dames Puma Sneakers[/url]
[url=]Nike Air Max 1 Dames Zomer[/url]
[url=]Adidas Originals Dragon Heren[/url]
[url=]Louis Vuitton Tas[/url]


Date: 2017-03-21 12:04 pm (UTC)
From: (Anonymous)

[url=]Nike Hyperadapt Pris[/url]
[url=]Adidas Primeknit Fs Uscita[/url]
[url=]New York Keps Snapback[/url]
[url=]Adidas Tubular Shadow Noir[/url]
[url=]Adidas Superstar 2 Nuevas[/url]


Date: 2017-03-21 09:56 pm (UTC)
From: (Anonymous)

[url=]Nike Flyknit Trainer White Black[/url]
[url=]Vans Sk8 Hi Rosa[/url]
[url=ß-silber-türkis-630.html]Nike Air Max Weiß Silber Türkis[/url]
[url=]Adidas Superstar Metallics - Dames Schoenen[/url]
[url=]Hollister Dames Jassen[/url]


Date: 2017-03-22 12:33 am (UTC)
From: (Anonymous)

[url=]Adidas Duramo 6 Herren Schwarz[/url]
[url=]Adidas Eqt Boost Ebay[/url]
[url=]Puma Creeper Rihanna[/url]
[url=]Nike Hyperadapt Demo[/url]
[url=]Nike Cortez Mujer Azul[/url]


Date: 2017-03-22 10:12 am (UTC)
From: (Anonymous)

[url=]Sneakers Dsquared2[/url]
[url=]Chaussure Louis Vuitton Pour Homme Prix[/url]
[url=]Clarks Desert Mali[/url]
[url=]Armani Jeans Baskets[/url]
[url=]Armani Basket Ea7[/url]


Date: 2017-03-26 03:38 am (UTC)
From: (Anonymous)

[url=]Basket New Balance Running Femme Pas Cher[/url]
[url=]Basket Louboutin Homme Rouge[/url]
[url=]Portefeuille Louis Vuitton Femme Noir[/url]
[url=]Louis Vuitton Alma[/url]
[url=]Lunette Lv Millionaire[/url]


Date: 2017-03-26 09:09 pm (UTC)
From: (Anonymous)

[url=]Oakley Jawbreaker Blanche[/url]
[url=]Converse Basse Blanche 36 Pas Cher[/url]
[url=é]Nike Huarache Bronze Doré[/url]
[url=]Nike Air Force One Suede Bleu[/url]
[url=]Nike Air Force Rose Fluo[/url]


Date: 2017-03-29 03:46 pm (UTC)
From: (Anonymous)

[url=]Sneakers Supra[/url]
[url=]Skechers Noir Et Rose[/url]
[url=]Mbt Pata[/url]
[url=]Coq Sportif Rose Pale Femme[/url]
[url=]Palladium Intersport[/url]


Date: 2017-03-31 05:09 am (UTC)
From: (Anonymous)

[url=]Puma Suede Creepers Velvet[/url]
[url=]Puma X Fenty Amazon[/url]
[url=]Creepers Puma Rojas[/url]
[url=]Puma Suede Classic Black And Gold[/url]
[url=]Puma Fenty Bordeaux Velour[/url]

April 2017

2345 678

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 18th, 2017 08:12 pm
Powered by Dreamwidth Studios