diff options
Diffstat (limited to 'doc/design-thoughts/pool-debugging.txt')
| -rw-r--r-- | doc/design-thoughts/pool-debugging.txt | 243 |
1 files changed, 243 insertions, 0 deletions
diff --git a/doc/design-thoughts/pool-debugging.txt b/doc/design-thoughts/pool-debugging.txt new file mode 100644 index 0000000..106e41c --- /dev/null +++ b/doc/design-thoughts/pool-debugging.txt @@ -0,0 +1,243 @@ +2022-02-22 - debugging options with pools + +Two goals: + - help developers spot bugs as early as possible + + - make the process more reliable in field, by killing sick ones as soon as + possible instead of letting them corrupt data, cause trouble, or even be + exploited. + +An allocated object may exist in 5 forms: + - in use: currently referenced and used by haproxy, 100% of its size are + dedicated to the application which can do absolutely anything with it, + but it may never touch anything before nor after that area. + + - in cache: the object is neither referenced nor used anymore, but it sits + in a thread's cache. The application may not touch it at all anymore, and + some parts of it could even be unmapped. Only the current thread may safely + reach it, though others might find/release it when under thread isolation. + The thread cache needs some LRU linking that may be stored anywhere, either + inside the area, or outside. The parts surrounding the <size> parts remain + invisible to the application layer, and can serve as a protection. + + - in shared cache: the object is neither referenced nor used anymore, but it + may be reached by any thread. Some parts of it could be unmapped. Any + thread may pick it but only one may find it, hence once grabbed, it is + guaranteed no other one will find it. The shared cache needs to set up a + linked list and a single pointer needs to be stored anywhere, either inside + or outside the area. The parts surrounding the <size> parts remain + invisible to the application layer, and can serve as a protection. + + - in the system's memory allocator: the object is not known anymore from + haproxy. It may be reassigned in parts or totally to other pools or other + subsystems (e.g. crypto library). Some or all of it may be unmapped. The + areas surrounding the <size> parts are also part of the object from the + library's point of view and may be delivered to other areas. Tampering + with these may cause any other part to malfunction in dirty ways. + + - in the OS only: the memory allocator gave it back to the OS. + +The following options need to be configurable: + - detect improper initialization: this is done by poisonning objects before + delivering them to the application. + + - help figure where an object was allocated when in use: a pointer to the + call place will help. Pointing to the last pool_free() as well for the + same reasons when dealing with a UAF. + + - detection of wrong pointer/pool when in use: a pointer to the pool before + or after the area will definitely help. + + - detection of overflows when in use: a canary at the end of the area + (closest possible to <size>) will definitely help. The pool above can do + that job. Ideally, we should fill some data at the end so that even + unaligned sizes can be checked (e.g. a buffer that gets a zero appended). + If we just align on 2 pointers, writing the same pointer twice at the end + may do the job, but we won't necessarily have our bytes. Thus a particular + end-of-string pattern would be useful (e.g. ff55aa01) to fill it. + + - detection of double free when in cache: similar to detection of wrong + pointer/pool when in use: the pointer at the end may simply be changed so + that it cannot match the pool anymore. By using a pointer to the caller of + the previous free() operation, we have the guarantee to see different + pointers, and this pointer can be inspected to figure where the object was + previously freed. An extra check may even distinguish a perfect double-free + (same caller) from just a wrong free (pointer differs from pool). + + - detection of late corruption when in cache: keeping a copy of the + checksum of the whole area upon free() will do the job, but requires one + extra storage area for the checksum. Filling the area with a pattern also + does the job and doesn't require extra storage, but it loses the contents + and can be a bit slower. Sometimes losing the contents can be a feature, + especially when trying to detect late reads. Probably that both need to + be implemented. Note that if contents are not strictly needed, storing a + checksum inside the area does the job. + + - preserve total contents in cache for debugging: losing some precious + information can be a problem. + + - pattern filling of the area helps detect use-after-free in read-only mode. + + - allocate cold first helps with both cases above. + +Uncovered: + - overflow/underflow when in cache/shared/libc: it belongs to use-after-free + pattern and such an error during regular use ought to be caught while the + object was still in use. + + - integrity when in libc: not under our control anymore, this is a libc + problem. + +Arbitrable: + - integrity when in shared cache: unlikely to happen only then if it could + have happened in the local cache. Shared cache not often used anymore, thus + probably not worth the effort + + - protection against double-free when in shared cache/libc: might be done for + a cheap price, probably worth being able to quickly tell that such an + object left the local cache (e.g. the mark points to the caller, but could + possibly just be incremented, hence still point to the same code location+1 + byte when released. Calls are 4 bytes min on RISC, 5 on x86 so we do have + some margin by having a caller's location be +0,+1,+2 or +3. + + - underflow when in use: hasn't been really needed over time but may change. + + - detection of late corruption when in shared cache: checksum or area filling + are possible, but is this as relevant as it used to considering the less + common use of the shared cache ? + +Design considerations: + - object allocation when in use must remain minimal + + - when in cache, there are 2 lists which the compiler expect to be at least + aligned each (e.g. if/when we start to use DWCAS). + + - the original "pool debugging" feature covers both pool tracking, double- + free detection, overflow detection and caller info at the cost of a single + pointer placed immediately after the area. + + - preserving the contents might be done by placing the cache links and the + shared cache's list outside of the area (either before or after). Placing + it before has the merit that the allocated object preserves the 4-ptr + alignment. But when a larger alignment is desired this often does not work + anymore. Placing it after requires some dynamic adjustment depending on the + object's size. If any protection is installed, this protection must be + placed before the links so that the list doesn't get randomly corrupted and + corrupts adjacent elements. Note that if protection is desired, the extra + waste is probably less critical. + + - a link to the last caller might have to be stored somewhere. Without + preservation the free() caller may be placed anywhere while the alloc() + caller may only be placed outside. With preservation, again the free() + caller may be placed either before the object or after the mark at the end. + There is no particular need that both share the same location though it may + help. Note that when debugging is enabled, the free() caller doesn't need + to be duplicated and can continue to serve as the double-free detection. + Thus maybe in the end we only need to store the caller to the last alloc() + but not the free() since if we want it it's available via the pool debug. + + - use-after-free detection: contents may be erased on free() and checked on + alloc(), but they can also be checksummed on free() and rechecked on + alloc(). In the latter case we need to store a checksum somewhere. Note + that with pure checksum we don't know what part was modified, but seeing + previous contents can be useful. + +Possibilities: + +1) Linked lists inside the area: + + V size alloc + ---+------------------------------+-----------------+-- + in use |##############################| (Pool) (Tracer) | + ---+------------------------------+-----------------+-- + + ---+--+--+------------------------+-----------------+-- + in cache |L1|L2|########################| (Caller) (Sum) | + ---+--+--+------------------------+-----------------+-- +or: + ---+--+--+------------------------+-----------------+-- + in cache |L1|L2|###################(sum)| (Caller) | + ---+--+--+------------------------+-----------------+-- + + ---+-+----------------------------+-----------------+-- + in global |N|XXXX########################| (Caller) | + ---+-+----------------------------+-----------------+-- + + +2) Linked lists before the the area leave room for tracer and pool before + the area, but the canary must remain at the end, however the area will + be more difficult to keep aligned: + + V head size alloc + ----+-+-+------------------------------+-----------------+-- + in use |T|P|##############################| (canary) | + ----+-+-+------------------------------+-----------------+-- + + --+-----+------------------------------+-----------------+-- + in cache |L1|L2|##############################| (Caller) (Sum) | + --+-----+------------------------------+-----------------+-- + + ------+-+------------------------------+-----------------+-- + in global |N|##############################| (Caller) | + ------+-+------------------------------+-----------------+-- + + +3) Linked lists at the end of the area, might be shared with extra data + depending on the state: + + V size alloc + ---+------------------------------+-----------------+-- + in use |##############################| (Pool) (Tracer) | + ---+------------------------------+-----------------+-- + + ---+------------------------------+--+--+-----------+-- + in cache |##############################|L1|L2| (Caller) (Sum) + ---+------------------------------+--+--+-----------+-- + + ---+------------------------------+-+---------------+-- + in global |##############################|N| (Caller) | + ---+------------------------------+-+---------------+-- + +This model requires a little bit of alignment at the end of the area, which is +not incompatible with pattern filling and/or checksumming: + - preserving the area for post-mortem analysis means nothing may be placed + inside. In this case it could make sense to always store the last releaser. + - detecting late corruption may be done either with filling or checksumming, + but the simple fact of assuming a risk of corruption that needs to be + chased means we must not store the lists nor caller inside the area. + +Some models imply dedicating some place when in cache: + - preserving contents forces the lists to be prefixed or appended, which + leaves unused places when in use. Thus we could systematically place the + pool pointer and the caller in this case. + + - if preserving contents is not desired, almost everything can be stored + inside when not in use. Then each situation's size should be calculated + so that the allocated size is known, and entries are filled from the + beginning while not in use, or after the size when in use. + + - if poisonning is requested, late corruption might be detected but then we + don't want the list to be stored inside at the risk of being corrupted. + +Maybe just implement a few models: + - compact/optimal: put l1/l2 inside + - detect late corruption: fill/sum, put l1/l2 out + - preserve contents: put l1/l2 out + - corruption+preserve: do not fill, sum out + - poisonning: not needed on free if pattern filling is done. + +try2: + - poison on alloc to detect missing initialization: yes/no + (note: nothing to do if filling done) + - poison on free to detect use-after-free: yes/no + (note: nothing to do if filling done) + - check on alloc for corruption-after-free: yes/no + If content-preserving => sum, otherwise pattern filling; in + any case, move L1/L2 out. + - check for overflows: yes/no: use a canary after the area. The + canary can be the pointer to the pool. + - check for alloc caller: yes/no => always after the area + - content preservation: yes/no + (disables filling, moves lists out) + - improved caller tracking: used to detect double-free, may benefit + from content-preserving but not only. |