From cda5d340e78555d2542be9264137319c5308e798 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 18:44:12 +0200 Subject: Adding upstream version 2.4.2. Signed-off-by: Daniel Baumann --- doc/context.png | Bin 0 -> 4715 bytes doc/context_tree.png | Bin 0 -> 6158 bytes doc/mainpage.dox | 111 ++++++++++++++++++++++ doc/stealing.png | Bin 0 -> 6994 bytes doc/tutorial_bestpractices.dox | 192 ++++++++++++++++++++++++++++++++++++++ doc/tutorial_context.dox | 198 ++++++++++++++++++++++++++++++++++++++++ doc/tutorial_debugging.dox | 116 +++++++++++++++++++++++ doc/tutorial_destructors.dox | 82 +++++++++++++++++ doc/tutorial_dts.dox | 109 ++++++++++++++++++++++ doc/tutorial_introduction.dox | 45 +++++++++ doc/tutorial_pools.dox | 93 +++++++++++++++++++ doc/tutorial_stealing.dox | 55 +++++++++++ doc/tutorial_threads.dox | 203 +++++++++++++++++++++++++++++++++++++++++ 13 files changed, 1204 insertions(+) create mode 100644 doc/context.png create mode 100644 doc/context_tree.png create mode 100644 doc/mainpage.dox create mode 100644 doc/stealing.png create mode 100644 doc/tutorial_bestpractices.dox create mode 100644 doc/tutorial_context.dox create mode 100644 doc/tutorial_debugging.dox create mode 100644 doc/tutorial_destructors.dox create mode 100644 doc/tutorial_dts.dox create mode 100644 doc/tutorial_introduction.dox create mode 100644 doc/tutorial_pools.dox create mode 100644 doc/tutorial_stealing.dox create mode 100644 doc/tutorial_threads.dox (limited to 'doc') diff --git a/doc/context.png b/doc/context.png new file mode 100644 index 0000000..48a6ca0 Binary files /dev/null and b/doc/context.png differ diff --git a/doc/context_tree.png b/doc/context_tree.png new file mode 100644 index 0000000..9723459 Binary files /dev/null and b/doc/context_tree.png differ diff --git a/doc/mainpage.dox b/doc/mainpage.dox new file mode 100644 index 0000000..ece6ccb --- /dev/null +++ b/doc/mainpage.dox @@ -0,0 +1,111 @@ +/** + * @mainpage + * + * talloc is a hierarchical, reference counted memory pool system with + * destructors. It is the core memory allocator used in Samba. + * + * @section talloc_download Download + * + * You can download the latest releases of talloc from the + * talloc directory + * on the samba public source archive. + * + * @section main-tutorial Tutorial + * + * You should start by reading @subpage libtalloc_tutorial, then reading the documentation of + * the interesting functions as you go. + + * @section talloc_bugs Discussion and bug reports + * + * talloc does not currently have its own mailing list or bug tracking system. + * For now, please use the + * samba-technical + * mailing list, and the + * Samba bugzilla + * bug tracking system. + * + * @section talloc_devel Development + * You can download the latest code either via git or rsync. + * + * To fetch via git see the following guide: + * + * Using Git for Samba Development + * + * Once you have cloned the tree switch to the master branch and cd into the + * lib/tevent directory. + * + * To fetch via rsync use this command: + * + * rsync -Pavz samba.org::ftp/unpacked/standalone_projects/lib/talloc . + * + * @section talloc_preample Preamble + * + * talloc is a hierarchical, reference counted memory pool system with + * destructors. + * + * Perhaps the biggest difference from other memory pool systems is that there + * is no distinction between a "talloc context" and a "talloc pointer". Any + * pointer returned from talloc() is itself a valid talloc context. This means + * you can do this: + * + * @code + * struct foo *X = talloc(mem_ctx, struct foo); + * X->name = talloc_strdup(X, "foo"); + * @endcode + * + * The pointer X->name would be a "child" of the talloc context "X" which is + * itself a child of mem_ctx. So if you do talloc_free(mem_ctx) then it is all + * destroyed, whereas if you do talloc_free(X) then just X and X->name are + * destroyed, and if you do talloc_free(X->name) then just the name element of + * X is destroyed. + * + * If you think about this, then what this effectively gives you is an n-ary + * tree, where you can free any part of the tree with talloc_free(). + * + * If you find this confusing, then run the testsuite to watch talloc in + * action. You may also like to add your own tests to testsuite.c to clarify + * how some particular situation is handled. + * + * @section talloc_performance Performance + * + * All the additional features of talloc() over malloc() do come at a price. We + * have a simple performance test in Samba4 that measures talloc() versus + * malloc() performance, and it seems that talloc() is about 4% slower than + * malloc() on my x86 Debian Linux box. For Samba, the great reduction in code + * complexity that we get by using talloc makes this worthwhile, especially as + * the total overhead of talloc/malloc in Samba is already quite small. + * + * @section talloc_named Named blocks + * + * Every talloc chunk has a name that can be used as a dynamic type-checking + * system. If for some reason like a callback function you had to cast a + * "struct foo *" to a "void *" variable, later you can safely reassign the + * "void *" pointer to a "struct foo *" by using the talloc_get_type() or + * talloc_get_type_abort() macros. + * + * @code + * struct foo *X = talloc_get_type_abort(ptr, struct foo); + * @endcode + * + * This will abort if "ptr" does not contain a pointer that has been created + * with talloc(mem_ctx, struct foo). + * + * @section talloc_threading Multi-threading + * + * talloc itself does not deal with threads. It is thread-safe (assuming the + * underlying "malloc" is), as long as each thread uses different memory + * contexts. + * + * If two threads uses the same context then they need to synchronize in order + * to be safe. In particular: + * + * - when using talloc_enable_leak_report(), giving directly NULL as a parent + * context implicitly refers to a hidden "null context" global variable, so + * this should not be used in a multi-threaded environment without proper + * synchronization. In threaded code turn off null tracking using + * talloc_disable_null_tracking(). + * - the context returned by talloc_autofree_context() is also global so + * shouldn't be used by several threads simultaneously without + * synchronization. + * + */ diff --git a/doc/stealing.png b/doc/stealing.png new file mode 100644 index 0000000..8833e06 Binary files /dev/null and b/doc/stealing.png differ diff --git a/doc/tutorial_bestpractices.dox b/doc/tutorial_bestpractices.dox new file mode 100644 index 0000000..3634446 --- /dev/null +++ b/doc/tutorial_bestpractices.dox @@ -0,0 +1,192 @@ +/** +@page libtalloc_bestpractices Chapter 7: Best practises + +The following sections contain several best practices and good manners that were +found by the Samba and +SSSD developers over the years. +These will help you to write code which is better, easier to debug and with as +few (hopefully none) memory leaks as possible. + +@section bp-hierarchy Keep the context hierarchy steady + +The talloc is a hierarchy memory allocator. The hierarchy nature is what makes +the programming more error proof. It makes the memory easier to manage and to +free. Therefore, the first thing we should have on our mind is: always project +your data structures into the talloc context hierarchy. + +That means if we have a structure, we should always use it as a parent context +for its elements. This way we will not encounter any troubles when freeing the +structure or when changing its parent. The same rule applies for arrays. + +For example, the structure user from section @ref context-hierarchy +should be created with the context hierarchy illustrated on the next image. + +@image html context_tree.png + +@section bp-tmpctx Every function should use its own context + +It is a good practice to create a temporary talloc context at the function +beginning and free the context just before the return statement. All the data +must be allocated on this context or on its children. This ensures that no +memory leaks are created as long as we do not forget to free the temporary +context. + +This pattern applies to both situations - when a function does not return any +dynamically allocated value and when it does. However, it needs a little +extension for the latter case. + +@subsection bp-tmpctx-1 Functions that do not return any dynamically allocated +value + +If the function does not return any value created on the heap, we will just obey +the aforementioned pattern. + +@code +int bar() +{ + int ret; + TALLOC_CTX *tmp_ctx = talloc_new(NULL); + if (tmp_ctx == NULL) { + ret = ENOMEM; + goto done; + } + /* allocate data on tmp_ctx or on its descendants */ + ret = EOK; +done: + talloc_free(tmp_ctx); + return ret; +} +@endcode + +@subsection bp-tmpctx-2 Functions returning dynamically allocated values + +If our function returns any dynamically allocated data, its first parameter +should always be the destination talloc context. This context serves as a parent +for the output values. But again, we will create the output values as the +descendants of the temporary context. If everything goes well, we will change +the parent of the output values from the temporary to the destination talloc +context. + +This pattern ensures that if an error occurs (e.g. I/O error or insufficient +amount of the memory), all allocated data is freed and no garbage appears on +the destination context. + +@code +int struct_foo_init(TALLOC_CTX *mem_ctx, struct foo **_foo) +{ + int ret; + struct foo *foo = NULL; + TALLOC_CTX *tmp_ctx = talloc_new(NULL); + if (tmp_ctx == NULL) { + ret = ENOMEM; + goto done; + } + foo = talloc_zero(tmp_ctx, struct foo); + /* ... */ + *_foo = talloc_steal(mem_ctx, foo); + ret = EOK; +done: + talloc_free(tmp_ctx); + return ret; +} +@endcode + +@section bp-null Allocate temporary contexts on NULL + +As it can be seen on the previous listing, instead of allocating the temporary +context directly on mem_ctx, we created a new top level context +using NULL as the parameter for talloc_new() function. +Take a look at the following example: + +@code +char *create_user_filter(TALLOC_CTX *mem_ctx, + uid_t uid, const char *username) +{ + char *filter = NULL; + char *sanitized_username = NULL; + /* tmp_ctx is a child of mem_ctx */ + TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx); + if (tmp_ctx == NULL) { + return NULL; + } + + sanitized_username = sanitize_string(tmp_ctx, username); + if (sanitized_username == NULL) { + talloc_free(tmp_ctx); + return NULL; + } + + filter = talloc_aprintf(tmp_ctx,"(|(uid=%llu)(uname=%s))", + uid, sanitized_username); + if (filter == NULL) { + return NULL; /* tmp_ctx is not freed */ (*@\label{lst:tmp-ctx-3:leak}@*) + } + + /* filter becomes a child of mem_ctx */ + filter = talloc_steal(mem_ctx, filter); + talloc_free(tmp_ctx); + return filter; +} +@endcode + +We forgot to free tmp_ctx before the return statement +in the filter == NULL condition. However, it is created as a child +of mem_ctx context and as such it will be freed as soon as the +mem_ctx is freed. Therefore, no detectable memory leak is created. + +On the other hand, we do not have any way to access the allocated data +and for all we know mem_ctx may exist for the lifetime of our +application. For these reasons this should be considered as a memory leak. How +can we detect if it is unreferenced but still attached to its parent context? +The only way is to notice the mistake in the source code. + +But if we create the temporary context as a top level context, it will not be +freed and memory diagnostic tools +(e.g. valgrind) are able to do their job. + +@section bp-pool Temporary contexts and the talloc pool + +If we want to take the advantage of the talloc pool but also keep to the +pattern introduced in the previous section, we are unable to do it directly. The +best thing to do is to create a conditional build where we can decide how do we +want to create the temporary context. For example, we can create the following +macros: + +@code +#ifdef USE_POOL_CONTEXT + #define CREATE_POOL_CTX(ctx, size) talloc_pool(ctx, size) + #define CREATE_TMP_CTX(ctx) talloc_new(ctx) +#else + #define CREATE_POOL_CTX(ctx, size) talloc_new(ctx) + #define CREATE_TMP_CTX(ctx) talloc_new(NULL) +#endif +@endcode + +Now if our application is under development, we will build it with macro +USE_POOL_CONTEXT undefined. This way, we can use memory diagnostic +utilities to detect memory leaks. + +The release version will be compiled with the macro defined. This will enable +pool contexts and therefore reduce the malloc() calls, which will +end up in a little bit faster processing. + +@code +int struct_foo_init(TALLOC_CTX *mem_ctx, struct foo **_foo) +{ + int ret; + struct foo *foo = NULL; + TALLOC_CTX *tmp_ctx = CREATE_TMP_CTX(mem_ctx); + /* ... */ +} + +errno_t handle_request(TALLOC_CTX mem_ctx) +{ + int ret; + struct foo *foo = NULL; + TALLOC_CTX *pool_ctx = CREATE_POOL_CTX(NULL, 1024); + ret = struct_foo_init(mem_ctx, &foo); + /* ... */ +} +@endcode + +*/ diff --git a/doc/tutorial_context.dox b/doc/tutorial_context.dox new file mode 100644 index 0000000..b8bfe26 --- /dev/null +++ b/doc/tutorial_context.dox @@ -0,0 +1,198 @@ +/** +@page libtalloc_context Chapter 1: Talloc context +@section context Talloc context + +The talloc context is the most important part of this library and is +responsible for every single feature of this memory allocator. It is a logical +unit which represents a memory space managed by talloc. + +From the programmer's point of view, the talloc context is completely +equivalent to a pointer that would be returned by the memory routines from the +C standard library. This means that every context that is returned from the +talloc library can be used directly in functions that do not use talloc +internally. For example we can do the following: + +@code +char *str1 = strdup("I am NOT a talloc context"); +char *str2 = talloc_strdup(NULL, "I AM a talloc context"); + +printf("%d\n", strcmp(str1, str2) == 0); + +free(str1); +talloc_free(str2); /* we can not use free() on str2 */ +@endcode + +This is possible because the context is internally handled as a special +fixed-length structure called talloc chunk. Each chunk stores context metadata +followed by the memory space requested by the programmer. When a talloc +function returns a context (pointer), it will in fact return a pointer to the user +space portion of the talloc chunk. If we to manipulate this context using +talloc functions, the talloc library transforms the user-space pointer back to +the starting address of the chunk. This is also the reason why we were unable +to use free(str2) in the previous example - because +str2 does not point at the beginning of the allocated block of +memory. This is illustrated on the next image: + +@image html context.png + +The type TALLOC_CTX is defined in talloc.h to identify a talloc context in +function parameters. However, this type is just an alias for void +and exists only for semantical reasons - thus we can differentiate between +void * (arbitrary data) and TALLOC_CTX * (talloc +context). + +@subsection metadata Context meta data + +Every talloc context carries several pieces of internal information along with +the allocated memory: + + - name - which is used in reports of context hierarchy and to simulate + a dynamic type system, + - size of the requested memory in bytes - this can be used to determine + the number of elements in arrays, + - attached destructor - which is executed just before the memory block is + about to be freed, + - references to the context + - children and parent contexts - create the hierarchical view on the + memory. + +@section context-hierarchy Hierarchy of talloc context + +Every talloc context contains information about its parent and children. Talloc +uses this information to create a hierarchical model of memory or to be more +precise, it creates an n-ary tree where each node represents a single talloc +context. The root node of the tree is referred to as a top level context - a +context without any parent. + +This approach has several advantages: + + - as a consequence of freeing a talloc context, all of its children + will be properly deallocated as well, + - the parent of a context can be changed at any time, which + results in moving the whole subtree under another node, + - it creates a more natural way of managing data structures. + +@subsection Example + +We have a structure that stores basic information about a user - his/her name, +identification number and groups he/she is a member of: + +@code +struct user { + uid_t uid; + char *username; + size_t num_groups; + char **groups; +}; +@endcode + +We will allocate this structure using talloc. The result will be the following +context tree: + +@image html context_tree.png + +@code +/* create new top level context */ +struct user *user = talloc(NULL, struct user); + +user->uid = 1000; +user->num_groups = N; + +/* make user the parent of following contexts */ +user->username = talloc_strdup(user, "Test user"); +user->groups = talloc_array(user, char*, user->num_groups); + +for (i = 0; i < user->num_groups; i++) { + /* make user->groups the parent of following context */ + user->groups[i] = talloc_asprintf(user->groups, + "Test group %d", i); +} +@endcode + +This way, we have gained a lot of additional capabilities, one of which is +very simple deallocation of the structure and all of its elements. + +With the C standard library we need first to iterate over the array of groups +and free every element separately. Then we must deallocate the array that stores +them. Next we deallocate the username and as the last step free the structure +itself. But with talloc, the only operation we need to execute is freeing the +structure context. Its descendants will be freed automatically. + +@code +talloc_free(user); +@endcode + +@section keep-hierarchy Always keep the hieararchy steady! + +The talloc is a hierarchy memory allocator. The hierarchy nature is what makes +the programming more error proof. It makes the memory easier to manage and to +free. Therefore, the first thing we should have on our mind is: always +project our data structures into the talloc context hierarchy. + +That means if we have a structure, we should always use it as a parent context +for its elements. This way we will not encounter any troubles when freeing this +structure or when changing its parent. The same rule applies for arrays. + +@section creating-context Creating a talloc context + +Here are the most important functions that create a new talloc context. + +@subsection type-safe Type-safe functions + +It allocates the size that is necessary for the given type and returns a new, +properly-casted pointer. This is the preferred way to create a new context as +we can rely on the compiler to detect type mismatches. + +The name of the context is automatically set to the name of the data type which +is used to simulate a dynamic type system. + +@code +struct user *user = talloc(ctx, struct user); + +/* initialize to default values */ +user->uid = 0; +user->name = NULL; +user->num_groups = 0; +user->groups = NULL; + +/* or we can achieve the same result with */ +struct user *user_zero = talloc_zero(ctx, struct user); +@endcode + +@subsection zero-length Zero-length contexts + +The zero-length context is basically a context without any special semantical +meaning. We can use it the same way as any other context. The only difference +is that it consists only of the meta data about the context. Therefore, it is +strictly of type TALLOC_CTX*. It is often used in cases where we +want to aggregate several data structures under one parent (zero-length) +context, such as a temporary context to contain memory needed within a single +function that is not interesting to the caller. Allocating on a zero-length +temporary context will make clean-up of the function simpler. + +@code +TALLOC_CTX *tmp_ctx = NULL; +struct foo *foo = NULL; +struct bar *bar = NULL; + +/* new zero-length top level context */ +tmp_ctx = talloc_new(NULL); +if (tmp_ctx == NULL) { + return ENOMEM; +} + +foo = talloc(tmp_ctx, struct foo); +bar = talloc(tmp_ctx, struct bar); + +/* free everything at once */ +talloc_free(tmp_ctx); +@endcode + +@subsection context-see-also See also + +- talloc_size() +- talloc_named() +- @ref talloc_array +- @ref talloc_string + +*/ diff --git a/doc/tutorial_debugging.dox b/doc/tutorial_debugging.dox new file mode 100644 index 0000000..aadbb0d --- /dev/null +++ b/doc/tutorial_debugging.dox @@ -0,0 +1,116 @@ +/** +@page libtalloc_debugging Chapter 6: Debugging + +Although talloc makes memory management significantly easier than the C standard +library, developers are still only humans and can make mistakes. Therefore, it +can be handy to know some tools for the inspection of talloc memory usage. + +@section log-abort Talloc log and abort + +We have already encountered the abort function in section @ref dts. +In that case it was used when a type mismatch was detected. However, talloc +calls this abort function in several more situations: + +- when the provided pointer is not a valid talloc context, +- when the meta data is invalid - probably due to memory corruption, +- and when an access after free is detected. + +The third one is probably the most interesting. It can help us with detecting +an attempt to double-free a context or any other manipulation with it via +talloc functions (using it as a parent, stealing it, etc.). + +Before the context is freed talloc sets a flag in the meta data. This is then +used to detect the access after free. It basically works on the assumption that +the memory stays unchanged (at least for a while) even when it is properly +deallocated. This will work even if the memory is filled with the value +specified in TALLOC_FREE_FILL environment variable, because it +fills only the data part and leaves the meta data intact. + +Apart from the abort function, talloc uses a log function to provide additional +information to the aforementioned violations. To enable logging we shall set the +log function with one of: + +- talloc_set_log_fn() +- talloc_set_log_stderr() + +The following code is a sample output of accessing a context after it has been +freed: + +@code +talloc_set_log_stderr(); +TALLOC_CTX *ctx = talloc_new(NULL); + +talloc_free(ctx); +talloc_free(ctx); + +results in: +talloc: access after free error - first free may be at ../src/main.c:55 +Bad talloc magic value - access after free +@endcode + +Another example is an invalid context: + +@code +talloc_set_log_stderr(); +TALLOC_CTX *ctx = talloc_new(NULL); +char *str = strdup("not a talloc context"); +talloc_steal(ctx, str); + +results in: +Bad talloc magic value - unknown value +@endcode + +@section reports Memory usage reports + +Talloc can print reports of memory usage of a specified talloc context to a +file (to stdout or stderr). The report can be +simple or full. The simple report provides information only about the context +itself and its direct descendants. The full report goes recursively through the +entire context tree. See: + +- talloc_report() +- talloc_report_full() + +We will use the following code to retrieve the sample report: + +@code +struct foo { + char *str; +}; + +TALLOC_CTX *ctx = talloc_new(NULL); +char *str = talloc_strdup(ctx, "my string"); +struct foo *foo = talloc_zero(ctx, struct foo); +foo->str = talloc_strdup(foo, "I am Foo"); +char *str2 = talloc_strdup(foo, "Foo is my parent"); + +/* print full report */ +talloc_report_full(ctx, stdout); +@endcode + +It will print a full report of ctx to the standard output. +The message should be similar to: + +@code +full talloc report on 'talloc_new: ../src/main.c:82' (total 46 bytes in 5 blocks) + struct foo contains 34 bytes in 3 blocks (ref 0) 0x1495130 + Foo is my parent contains 17 bytes in 1 blocks (ref 0) 0x1495200 + I am Foo contains 9 bytes in 1 blocks (ref 0) 0x1495190 + my string contains 10 bytes in 1 blocks (ref 0) 0x14950c0 +@endcode + +We can notice in this report that something is wrong with the context containing +struct foo. We know that the structure has only one string element. +However, we can see in the report that it has two children. This indicates that +we have either violated the memory hierarchy or forgotten to free it as +temporary data. Looking into the code, we can see that

"Foo is my parent"
+

should be attached to ctx. + +See also: + +- talloc_enable_null_tracking() +- talloc_disable_null_tracking() +- talloc_enable_leak_report() +- talloc_enable_leak_report_full() + +*/ diff --git a/doc/tutorial_destructors.dox b/doc/tutorial_destructors.dox new file mode 100644 index 0000000..ed06387 --- /dev/null +++ b/doc/tutorial_destructors.dox @@ -0,0 +1,82 @@ +/** +@page libtalloc_destructors Chapter 4: Using destructors + +@section destructors Using destructors + +Destructors are well known methods in the world of object oriented programming. +A destructor is a method of an object that is automatically run when the object +is destroyed. It is usually used to return resources taken by the object back to +the system (e.g. closing file descriptors, terminating connection to a database, +deallocating memory). + +With talloc we can take the advantage of destructors even in C. We can easily +attach our own destructor to a talloc context. When the context is freed, the +destructor will run automatically. + +To attach/detach a destructor to a talloc context use: talloc_set_destructor(). + +@section destructors-example Example + +Imagine that we have a dynamically created linked list. Before we deallocate an +element of the list, we need to make sure that we have successfully removed it +from the list. Normally, this would be done by two commands in the exact order: +remove it from the list and then free the element. With talloc, we can do this +at once by setting a destructor on the element which will remove it from the +list and talloc_free() will do the rest. + +The destructor would be: + +@code +int list_remove(void *ctx) +{ + struct list_el *el = NULL; + el = talloc_get_type_abort(ctx, struct list_el); + /* remove element from the list */ +} +@endcode + +GCC version 3 and newer can check for the types during the compilation. So if +it is our major compiler, we can use a more advanced destructor: + +@code +int list_remove(struct list_el *el) +{ + /* remove element from the list */ +} +@endcode + +Now we will assign the destructor to the list element. We can do this directly +in the function that inserts it. + +@code +struct list_el* list_insert(TALLOC_CTX *mem_ctx, + struct list_el *where, + void *ptr) +{ + struct list_el *el = talloc(mem_ctx, struct list_el); + el->data = ptr; + /* insert into list */ + + talloc_set_destructor(el, list_remove); + return el; +} +@endcode + +Because talloc is a hierarchical memory allocator, we can go a step further and +free the data with the element as well: + +@code +struct list_el* list_insert_free(TALLOC_CTX *mem_ctx, + struct list_el *where, + void *ptr) +{ + struct list_el *el = NULL; + el = list_insert(mem_ctx, where, ptr); + + talloc_steal(el, ptr); + + return el; +} +@endcode + +*/ diff --git a/doc/tutorial_dts.dox b/doc/tutorial_dts.dox new file mode 100644 index 0000000..75b5172 --- /dev/null +++ b/doc/tutorial_dts.dox @@ -0,0 +1,109 @@ +/** +@page libtalloc_dts Chapter 3: Dynamic type system + +@section dts Dynamic type system + +Generic programming in the C language is very difficult. There is no inheritance +nor templates known from object oriented languages. There is no dynamic type +system. Therefore, generic programming in this language is usually done by +type-casting a variable to void* and transferring it through +a generic function to a specialized callback as illustrated on the next listing. + +@code +void generic_function(callback_fn cb, void *pvt) +{ + /* do some stuff and call the callback */ + cb(pvt); +} + +void specific_callback(void *pvt) +{ + struct specific_struct *data; + data = (struct specific_struct*)pvt; + /* ... */ +} + +void specific_function() +{ + struct specific_struct data; + generic_function(callback, &data); +} +@endcode + +Unfortunately, the type information is lost as a result of this type cast. The +compiler cannot check the type during the compilation nor are we able to do it +at runtime. Providing an invalid data type to the callback will result in +unexpected behaviour (not necessarily a crash) of the application. This mistake +is usually hard to detect because it is not the first thing which comes the +mind. + +As we already know, every talloc context contains a name. This name is available +at any time and it can be used to determine the type of a context even if we +lose the type of a variable. + +Although the name of the context can be set to any arbitrary string, the best +way of using it to simulate the dynamic type system is to set it directly to the +type of the variable. + +It is recommended to use one of talloc() and talloc_array() (or its +variants) to create the context as they set its name to the name of the +given type automatically. + +If we have a context with such as a name, we can use two similar functions that +do both the type check and the type cast for us: + +- talloc_get_type() +- talloc_get_type_abort() + +@section dts-examples Examples + +The following example will show how generic programming with talloc is handled - +if we provide invalid data to the callback, the program will be aborted. This +is a sufficient reaction for such an error in most applications. + +@code +void foo_callback(void *pvt) +{ + struct foo *data = talloc_get_type_abort(pvt, struct foo); + /* ... */ +} + +int do_foo() +{ + struct foo *data = talloc_zero(NULL, struct foo); + /* ... */ + return generic_function(foo_callback, data); +} +@endcode + +But what if we are creating a service application that should be running for the +uptime of a server, we may want to abort the application during the development +process (to make sure the error is not overlooked) and try to recover from the +error in the customer release. This can be achieved by creating a custom abort +function with a conditional build. + +@code +void my_abort(const char *reason) +{ + fprintf(stderr, "talloc abort: %s\n", reason); +#ifdef ABORT_ON_TYPE_MISMATCH + abort(); +#endif +} +@endcode + +The usage of talloc_get_type_abort() would be then: + +@code +talloc_set_abort_fn(my_abort); + +TALLOC_CTX *ctx = talloc_new(NULL); +char *str = talloc_get_type_abort(ctx, char); +if (str == NULL) { + /* recovery code */ +} +/* talloc abort: ../src/main.c:25: Type mismatch: + name[talloc_new: ../src/main.c:24] expected[char] */ +@endcode + +*/ diff --git a/doc/tutorial_introduction.dox b/doc/tutorial_introduction.dox new file mode 100644 index 0000000..418c38b --- /dev/null +++ b/doc/tutorial_introduction.dox @@ -0,0 +1,45 @@ +/** +@page libtalloc_tutorial The Tutorial +@section introduction Introduction + +Talloc is a hierarchical, reference counted memory pool system with destructors. +It is built atop the C standard library and it defines a set of utility +functions that altogether simplifies allocation and deallocation of data, +especially for complex structures that contain many dynamically allocated +elements such as strings and arrays. + +The main goals of this library are: removing the needs for creating a cleanup +function for every complex structure, providing a logical organization of +allocated memory blocks and reducing the likelihood of creating memory leaks in +long-running applications. All of this is achieved by allocating memory in a +hierarchical structure of talloc contexts such that deallocating one context +recursively frees all of its descendants as well. + +@section main-features Main features +- An open source project +- A hierarchical memory model +- Natural projection of data structures into the memory space +- Simplifies memory management of large data structures +- Automatic execution of a destructor before the memory is freed +- Simulates a dynamic type system +- Implements a transparent memory pool + +@section toc Table of contents: + +@subpage libtalloc_context + +@subpage libtalloc_stealing + +@subpage libtalloc_dts + +@subpage libtalloc_destructors + +@subpage libtalloc_pools + +@subpage libtalloc_debugging + +@subpage libtalloc_bestpractices + +@subpage libtalloc_threads + +*/ diff --git a/doc/tutorial_pools.dox b/doc/tutorial_pools.dox new file mode 100644 index 0000000..a0d1e1a --- /dev/null +++ b/doc/tutorial_pools.dox @@ -0,0 +1,93 @@ +/** +@page libtalloc_pools Chapter 5: Memory pools + +@section pools Memory pools + +Allocation of a new memory is an expensive operation and large programs can +contain thousands of calls of malloc() for a single computation, where every +call allocates only a very small amount of the memory. This can result in an +undesirable slowdown of the application. We can avoid this slowdown by +decreasing the number of malloc() calls by using a memory pool. + +A memory pool is a preallocated memory space with a fixed size. If we need to +allocate new data we will take the desired amount of the memory from the pool +instead of requesting a new memory from the system. This is done by creating a +pointer that points inside the preallocated memory. Such a pool must not be +reallocated as it would change its location - pointers that were pointing +inside the pool would become invalid. Therefore, a memory pool requires a very +good estimate of the required memory space. + +The talloc library contains its own implementation of a memory pool. It is +highly transparent for the programmer. The only thing that needs to be done is +an initialization of a new pool context using talloc_pool() - +which can be used in the same way as any other context. + +Refactoring of existing code (that uses talloc) to take the advantage of a +memory pool is quite simple due to the following properties of the pool context: + +- if we are allocating data on a pool context, it takes the desired + amount of memory from the pool, +- if the context is a descendant of the pool context, it takes the space + from the pool as well, +- if the pool does not have sufficient portion of memory left, it will + create a new non-pool context, leaving the pool intact + +@code +/* allocate 1KiB in a pool */ +TALLOC_CTX *pool_ctx = talloc_pool(NULL, 1024); + +/* Take 512B from the pool, 512B is left there */ +void *ptr = talloc_size(pool_ctx, 512); + +/* 1024B > 512B, this will create new talloc chunk outside + the pool */ +void *ptr2 = talloc_size(ptr, 1024); + +/* The pool still contains 512 free bytes + * this will take 200B from them. */ +void *ptr3 = talloc_size(ptr, 200); + +/* This will destroy context 'ptr3' but the memory + * is not freed, the available space in the pool + * will increase to 512B. */ +talloc_free(ptr3); + +/* This will free memory taken by 'pool_ctx' + * and 'ptr2' as well. */ +talloc_free(pool_ctx); +@endcode + +The above given is very convenient, but there is one big issue to be kept in +mind. If the parent of a talloc pool child is changed to a parent that is +outside of this pool, the whole pool memory will not be freed until the child is +freed. For this reason we must be very careful when stealing a descendant of a +pool context. + +@code +TALLOC_CTX *mem_ctx = talloc_new(NULL); +TALLOC_CTX *pool_ctx = talloc_pool(NULL, 1024); +struct foo *foo = talloc(pool_ctx, struct foo); + +/* mem_ctx is not in the pool */ +talloc_steal(mem_ctx, foo); + +/* pool_ctx is marked as freed but the memory is not + deallocated, accessing the pool_ctx again will cause + an error */ +talloc_free(pool_ctx); + +/* This deallocates the pool_ctx. */ +talloc_free(mem_ctx); +@endcode + +It may often be better to copy the memory we want instead of stealing it to +avoid this problem. If we do not need to retain the context name (to keep the +type information), we can use talloc_memdup() to do this. + +Copying the memory out of the pool may, however, discard all the performance +boost given by the pool, depending on the size of the copied memory. Therefore, +the code should be well profiled before taking this path. In general, the +golden rule is: if we need to steal from the pool context, we should not +use a pool context. + +*/ diff --git a/doc/tutorial_stealing.dox b/doc/tutorial_stealing.dox new file mode 100644 index 0000000..67eae1d --- /dev/null +++ b/doc/tutorial_stealing.dox @@ -0,0 +1,55 @@ +/** +@page libtalloc_stealing Chapter 2: Stealing a context + +@section stealing Stealing a context + +Talloc has the ability to change the parent of a talloc context to another +one. This operation is commonly referred to as stealing and it is one of +the most important actions performed with talloc contexts. + +Stealing a context is necessary if we want the pointer to outlive the context it +is created on. This has many possible use cases, for instance stealing a result +of a database search to an in-memory cache context, changing the parent of a +field of a generic structure to a more specific one or vice-versa. The most +common scenario, at least in Samba, is to steal output data from a function-specific +context to the output context given as an argument of that function. + +@code +struct foo { + char *a1; + char *a2; + char *a3; +}; + +struct bar { + char *wurst; + struct foo *foo; +}; + +struct foo *foo = talloc_zero(ctx, struct foo); +foo->a1 = talloc_strdup(foo, "a1"); +foo->a2 = talloc_strdup(foo, "a2"); +foo->a3 = talloc_strdup(foo, "a3"); + +struct bar *bar = talloc_zero(NULL, struct bar); +/* change parent of foo from ctx to bar */ +bar->foo = talloc_steal(bar, foo); + +/* or do the same but assign foo = NULL */ +bar->foo = talloc_move(bar, &foo); +@endcode + +The talloc_move() function is similar to the talloc_steal() function but +additionally sets the source pointer to NULL. + +In general, the source pointer itself is not changed (it only replaces the +parent in the meta data). But the common usage is that the result is +assigned to another variable, thus further accessing the pointer from the +original variable should be avoided unless it is necessary. In this case +talloc_move() is the preferred way of stealing a context. Additionally sets the +source pointer to NULL, thus.protects the pointer from being accidentally freed +and accessed using the old variable after its parent has been changed. + +@image html stealing.png + +*/ diff --git a/doc/tutorial_threads.dox b/doc/tutorial_threads.dox new file mode 100644 index 0000000..111bbf5 --- /dev/null +++ b/doc/tutorial_threads.dox @@ -0,0 +1,203 @@ +/** +@page libtalloc_threads Chapter 8: Using threads with talloc + +@section Talloc and thread safety + +The talloc library is not internally thread-safe, in that accesses +to variables on a talloc context are not controlled by mutexes or +other thread-safe primitives. + +However, so long as talloc_disable_null_tracking() is called from +the main thread to disable global variable access within talloc, +then each thread can safely use its own top level talloc context +allocated off the NULL context. + +For example: + +@code +static void *thread_fn(void *arg) +{ + const char *ctx_name = (const char *)arg; + /* + * Create a new top level talloc hierarchy in + * this thread. + */ + void *top_ctx = talloc_named_const(NULL, 0, "top"); + if (top_ctx == NULL) { + return NULL; + } + sub_ctx = talloc_named_const(top_ctx, 100, ctx_name); + if (sub_ctx == NULL) { + return NULL; + } + + /* + * Do more processing/talloc calls on top_ctx + * and its children. + */ + ...... + + talloc_free(top_ctx); + return value; +} +@endcode + +is a perfectly safe use of talloc within a thread. + +The problem comes when one thread wishes to move some +memory allocated on its local top level talloc context +to another thread. Care must be taken to add data access +exclusion to prevent memory corruption. One method would +be to lock a mutex before any talloc call on each thread, +but this would push the burden of total talloc thread-safety +on the poor user of the library. + +A much easier way to transfer talloced memory between +threads is by the use of an intermediate, mutex locked, +intermediate variable. + +An example of this is below - taken from test code inside +the talloc testsuite. + +The main thread creates 1000 sub-threads, and then accepts +the transfer of some thread-talloc'ed memory onto its top +level context from each thread in turn. + +A pthread mutex and condition variable are used to +synchronize the transfer via the intermediate_ptr +variable. + +@code +/* Required sync variables. */ +static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER; +static pthread_cond_t condvar = PTHREAD_COND_INITIALIZER; + +/* Intermediate talloc pointer for transfer. */ +static void *intermediate_ptr; + +/* Subthread. */ +static void *thread_fn(void *arg) +{ + int ret; + const char *ctx_name = (const char *)arg; + void *sub_ctx = NULL; + /* + * Do stuff that creates a new talloc hierarchy in + * this thread. + */ + void *top_ctx = talloc_named_const(NULL, 0, "top"); + if (top_ctx == NULL) { + return NULL; + } + sub_ctx = talloc_named_const(top_ctx, 100, ctx_name); + if (sub_ctx == NULL) { + return NULL; + } + + /* + * Now transfer a pointer from our hierarchy + * onto the intermediate ptr. + */ + ret = pthread_mutex_lock(&mtx); + if (ret != 0) { + talloc_free(top_ctx); + return NULL; + } + + /* Wait for intermediate_ptr to be free. */ + while (intermediate_ptr != NULL) { + ret = pthread_cond_wait(&condvar, &mtx); + if (ret != 0) { + talloc_free(top_ctx); + return NULL; + } + } + + /* and move our memory onto it from our toplevel hierarchy. */ + intermediate_ptr = talloc_move(NULL, &sub_ctx); + + /* Tell the main thread it's ready for pickup. */ + pthread_cond_broadcast(&condvar); + pthread_mutex_unlock(&mtx); + + talloc_free(top_ctx); + return NULL; +} + +/* Main thread. */ + +#define NUM_THREADS 1000 + +static bool test_pthread_talloc_passing(void) +{ + int i; + int ret; + char str_array[NUM_THREADS][20]; + pthread_t thread_id; + void *mem_ctx; + + /* + * Important ! Null tracking breaks threaded talloc. + * It *must* be turned off. + */ + talloc_disable_null_tracking(); + + /* Main thread toplevel context. */ + mem_ctx = talloc_named_const(NULL, 0, "toplevel"); + if (mem_ctx == NULL) { + return false; + } + + /* + * Spin off NUM_THREADS threads. + * They will use their own toplevel contexts. + */ + for (i = 0; i < NUM_THREADS; i++) { + (void)snprintf(str_array[i], + 20, + "thread:%d", + i); + if (str_array[i] == NULL) { + return false; + } + ret = pthread_create(&thread_id, + NULL, + thread_fn, + str_array[i]); + if (ret != 0) { + return false; + } + } + + /* Now wait for NUM_THREADS transfers of the talloc'ed memory. */ + for (i = 0; i < NUM_THREADS; i++) { + ret = pthread_mutex_lock(&mtx); + if (ret != 0) { + talloc_free(mem_ctx); + return false; + } + + /* Wait for intermediate_ptr to have our data. */ + while (intermediate_ptr == NULL) { + ret = pthread_cond_wait(&condvar, &mtx); + if (ret != 0) { + talloc_free(mem_ctx); + return false; + } + } + + /* and move it onto our toplevel hierarchy. */ + (void)talloc_move(mem_ctx, &intermediate_ptr); + + /* Tell the sub-threads we're ready for another. */ + pthread_cond_broadcast(&condvar); + pthread_mutex_unlock(&mtx); + } + + /* Dump the hierarchy. */ + talloc_report(mem_ctx, stdout); + talloc_free(mem_ctx); + return true; +} +@endcode +*/ -- cgit v1.2.3