summaryrefslogtreecommitdiffstats
path: root/doc/design-thoughts/pool-debugging.txt
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 12:18:05 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 12:18:05 +0000
commitb46aad6df449445a9fc4aa7b32bd40005438e3f7 (patch)
tree751aa858ca01f35de800164516b298887382919d /doc/design-thoughts/pool-debugging.txt
parentInitial commit. (diff)
downloadhaproxy-b46aad6df449445a9fc4aa7b32bd40005438e3f7.tar.xz
haproxy-b46aad6df449445a9fc4aa7b32bd40005438e3f7.zip
Adding upstream version 2.9.5.upstream/2.9.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'doc/design-thoughts/pool-debugging.txt')
-rw-r--r--doc/design-thoughts/pool-debugging.txt243
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.