0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsCopyright (C) 2003, 2004, 2016 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsThis Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsLicense, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrewsfile, You can obtain one at http://mozilla.org/MPL/2.0/.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews$Id: HOW-ADB-WORKS.txt,v 1.2 2004/03/05 05:04:50 marka Exp $
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffRecently, several groups have expressed concern over potential
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffdenial of service attacks within BIND 9, specifically within the ADB
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff(address database.) This document hopes to provide a more clear
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffpicture of how the ADB works, and what sort of attacks are less likely
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffdue to its use.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffWe will describe two scenarios, one with two CPUs (and therefore two
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffworker threads in BIND 9) and one with a single CPU (and therefore one
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffworker thread.) The two CPU scenario scales to N CPUs.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe ADB acts as a cache for nameserver lookups. If BIND 9 wishes to
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffcontact host ns1.example.com, it looks this name up in the ADB. It
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffwill either return a set of addresses (if known) or return a result
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffindicating a callback will occur when the data is found.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffADB query, data not found, no fetches pending
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff---------------------------------------------
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe name is hashed to find the "bucket" the name exists in. Each
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffbucket is a linked list of names. There are 1009 buckets in the ADB.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffOnce the bucket is found, it is locked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe linked list is searched to see if any addresses are known for the
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffname. If no information is found, a new fetch is started to find the
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffaddresses for this name.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe bucket is unlocked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffAt some point, a callback occurs. The end result is either a set of
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffaddresses for this name, or failure.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffNOTE: The bucket is NOT locked while the fetch is in progress.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffADB query, no data found, fetches pending
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff-----------------------------------------
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe name is hashed to find the "bucket" the name exists in. Each
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffbucket is a linked list of names. There are 1009 buckets in the ADB.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffOnce the bucket is found, it is locked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe linked list is searched to see if any addresses are known for the
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffname. If an in-progress fetch is found, we schedule a callback when
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffthe fetch completes. This means ONE fetch is in progress for any
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffspecific name.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe bucket is unlocked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffAt some point, a callback occurs. The end result is either a set of
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffaddresses for this name, or failure.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffNOTE: The bucket is NOT locked while the fetch is in progress.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffADB query, addresses found
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff--------------------------
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe name is hashed to find the "bucket" the name exists in. Each
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffbucket is a linked list of names. There are 1009 buckets in the ADB.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffOnce the bucket is found, it is locked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe linked list is searched. Since addresses are found, they are
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffcopied (referenced, actually) for the caller.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThe bucket is unlocked.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffNOTE: The bucket is NOT locked while the addresses are used by the
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffFor any single ADB lookup, at most one bucket is locked. If there are
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff10 worker threads, at most 10 buckets will be locked, and at most 9
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffCPUs will be waiting for a lock if they all happen to want the same
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffbucket. The wait time is fairly small, however, since it consists of:
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff linked list search
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff perhaps starting a fetch
5585e5da649f170b57a6b70d2014729956c621a7Michael Graff perhaps copying addresses
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffWhen BIND 9 is told to use two worker threads, each runs independently
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffof one another until shared data needs to be accessed. One place this
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffoccurs is in the ADB.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffIf both worker threads are trying to look up the same name (or two
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffnames that hash to the same ADB bucket) one will have to wait for the
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffADB lookup to complete. Note that the lock is NOT held while the
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffactual DNS fetch for the data is performed.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffIf they are looking up different names (that hash to different
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffbuckets) each runs independently.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffThis reduces the two CPU case to (at worse) a single CPU performance.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffOne CPU means one worker thread in operation, so there is no lock
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffAs described above, a N-CPU configuration will at worse fall back to a
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffone-CPU scenario while trying to access the same ADB bucket. However,
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffwhile the packet is decoded, data is retrieved from authority or cache
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffdata, and while the result is encoded into wire format and transmitted
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffto the caller, no ADB locks are held, and other CPUs are free to use
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffAt worse, all the CPUs but one will be blocking on an ADB lock.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffHowever, the time it takes to search authority and cache, decode and
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffencode a DNS packet is likely larger than the time taken in the ADB
5585e5da649f170b57a6b70d2014729956c621a7Michael Grafflock, so the worse case is unlikely to occur in practice.
5585e5da649f170b57a6b70d2014729956c621a7Michael GraffAlso, note that one the data is cached for a given query, the ADB is
5585e5da649f170b57a6b70d2014729956c621a7Michael Graffnot even used until that cache data expires.