---------------------------------------------------------------------------- Proposal for a coherent and extensible object memory management model for the FreeType engine. Draft 0. ------------------------------------------------------------------------- Introduction : FreeType's engine's current implementation uses a simple growing heap, called the "Font Pool". This pool allows easy but very limited memory management. Now that we have introduced features to support multiple opened fonts and even re-entrant builds, it becomes important to be able to manage several objects with much more flexibility. This text is an overview of the current problems that we're now faced with, as well as a proposal for a new memory model. This document is named 'draft 0', which means that you're welcome to add your comments and suggestions... I. The problems: A TrueType font file is reflected in memory by a large set of structures of various kinds and extents. Each of these structures can be seen as an 'object' which must be managed according to its function and some choices we may make in the process of developing the library. Because the FreeType library should be as easily extended as possible, we must provide an object management scheme that is both simple and extensible. We'll start by classifying the data that we manage into several groups to present many problems introduced by the requirements of extensibility. a. According to domain: It is important first to separate our data depending on some few high-level abstractions that reflect the goal of the library. - font/face data (a.k.a resident data): This label groups all the data that is relative to a given face, regardless of device resolutions or specific sizes. In our current implementation, this data is a tree of objects which root is a 'TResident_Record'. The name 'resident' comes from the fact that I thought, initially, that face data could be created and loaded in a single step, and would not require additional i/o operations later (unlike instance data, which needs much 'on-the-fly loading'). Though this is still the case, some new introductions could require more flexibility. Examples: Font Header, Maximum Profile, OS/2 Table, Font Program, CVT Program, Control Value Table (unscaled), Kerning, horizontal & vertical headers, etc. - pointsize data (a.k.a instance data): This data is specific to a given device resolution and/or point size. This regroups a lot of data that must be loaded on demand, depending on some attributes like glyph number, character mapping table, pixels per EM, etc. The sizes of the required instance objects can change greatly from one rendering/loading/computation to another. A very straightforward implementation would lead to a great number of calls of the 'malloc' and 'free' functions, with a wide distribution of memory blocks sizes. This usually leads to early fragmentation, slower performance, and memory 'spreading'. However, one very nice thing in the TrueType spec is that the 'Maximum Profile' table gives a lot of information that helps in computing the maximum size of a face's instance objects. It is thus possible to pre-allocate enough space for all instance objects and re-use it for each new instance operation. In our current implementation, instance data is a tree of objects which root is a 'TInstance_Record'. We currently use the growing heap to allocate all instance objects after the record, in what is called the 'instance segment'. Examples: scaled CVT, coordinates and flag arrays, contour arrays, instruction coderange, graphics state, device resolutions, compensations, pointsize and ppem dependent tables, ... - transient data (like execution contexts): Some data is only necessary for some specific operation, and doesn't need to be kept with other font or instance objects. For example, the execution stack used to interpret TrueType opcodes during hinting typically needs about 7 Kb. Now imagine a desktop publishing application, or a word processor, that can easily keep more than a dozen opened font instances for its work. If we give each instance its own execution stack, we'll take more than 80 Kb of memory that will be mainly unused, as hinting on all instances will be very rarely, if ever, requested at the same moment (even assuming a completely re-entrant build of the library). It is much better in this case to be able to ask for an on-demand execution stack when a new hinting operation is queried. On a larger scope, this sort of data is called 'transient', though transience doesn't represent a domain entirely. Transient data is used only on specific purpose. It should be possible to manage it efficiently, with schemes like caching. That's the reason why the 'execution context' record has been recently introduced in the implementation. Though all transient data is currently allocated with the instance one, it should be later possible to change its management. b. According to size/storage: - static data: These are structs usually defined in the TrueType specs, or for our own purposes. Their size and layout is fixed and is the same for all font objects that use them. They may contain pointers to some other tables, or simply some other static structures... Examples: Font Header, Maximum Profile, Horizontal Header, Graphics State, Execution Context, Resident Record, Instance Record, ... - linear data: These are arrays of simple static data. Their size is proportional to one of the font's properties, like the number of glyphs, the maximum number of points, etc. Examples: Glyph Locations, Coordinates and Flags arrays, Contour array, ... - attribute data: Data found in the TrueType file in a simple form, but which size varies with the nature and origin of the font. Attribute data is usually put in the resident data. Note: It *doesn't* contain pointers! Attribute data can be shared by instances, or replicated (e.g. the CVT: while the original is kept in the resident segment, scaled tables are found in the instance data). Note that the objects that are created to store all iterations of instance data operations (like glyph instructions arrays, execution stacks, etc.) are classified as 'attribute' objects too. However, the data that usually comes from the font file and is stored in the attribute objects (e.g. glyph instructions) belongs not to this class. 'Attribute' is a common label for all properties shared by all instances of a font, though their size isn't either static or linear. A glyph's instruction set is not a common property (it's even glyph dependent, not instance dependent), however, the maximum size of the glyph code range _is_ ... Example: Font program, CVT program, Control Value Table, ... - hybrid data: All data that doesn't come in one of the three previous forms. Usually, hybrid data are made of a static part and one or more linear parts of varying sizes. Examples: HMTX Table, Character Mappings, Embedded bitmaps,... It is sometimes difficult to pre-compute the maximum size of some of the hybrid data. The memory structures that manipulate them must then be coded with greater care. c. According to management: Several different management issues arise, depending on the nature and use of some of our objects: - Shared objects: We need a scheme that let us share some objects easily. For example, all instances of a same face point to the same parent resident record. It is important to see that we don't know completely how the FreeType engine is going to be extended in the future; this means that among all of the well-known techniques used to manage sharing, one should focus on these that can provide a good separation between implementation and semantics. - Cached objects: As seen previously in the description of transient data, it may be necessary or useful to cache some important data structures. As for sharing, it should be noted that the most interesting techniques are those that allow us to extend and change the management of various objects in the simplest way. II. Some proposed solutions: 1. Separating implementation from use whenever possible: It is, IMHO, very important to be able to separate the way we use our objects from the way they are indeed implemented. For example, as we're heading towards multiple builds of the same library (singly-threaded, thread-safe, and re-entrant) through the use of macros, it is much better to be able to have as few #ifdefs as possible. Not only do they make the code difficult to read and understand, they also make it much harder to maintain and extend. Only by carefully selecting our macros and their use can we craft a convenient engine. It probably is a bad thing to cast details about sharing and caching within a lot of routines when it's perfectly possible to gather them in specific portions of the code that are called by the rest of the library. The following proposals are inspired by this idea: a. Implementing sharing and caching of objects: Consider the case of tracking the instances of a given face. We could be happy by managing a simple reference counter in each TResident_Record. The counter would be incremented on instance creation, and decremented on instance deletion. A zeroed counter would imply an unused face object that could then be discarded. A re-entrant build would require the use of an additionnal mutex to protect the counter, but this wouldn't need that much work. However, we may also need to maintain a list of these instances, to be able to close all of them at once when desired (either through an API call like "Close_Face", or when the library detects a broken or corrupt font file). This is a different management choice. Both choices have their benefit and cost, and could be required by the nature of the system we want to write a font server for. The idea is to be able to change the implemented scheme easily. In order to do that, I recommend that we define some simple specific components, called 'managers', that could be used to perform the low-level tracking operation, while providing a simple API to the rest of the library, e.g. an 'instance' manager could provide the following functions: PInstance_Record New_Instance( PResident_Record face ); // Return a new instance record for a given face // The record is the root of a tree of instance objects // that are allocated/recycled by the manager. void Done_Instance( PInstance_Record this ); // Discards or recycles an instance's data. The owner // resident data can be discarded when zeroed depending // on the chosen implementation within the manager. PExecution_Context New_Execution( PInstance_Record instance ); // Queries a new execution context for a given instance object // This should be called before a new execution. The execution // context could be allocated on the fly. void Done_Execution( PInstance_Record instance ); // Discards or recycles an execution context previously // queried through 'New_Execution'. The implementation of these functions could deal with all the details regarding sharing and caching, while the rest of the library would be freed from these considerations. Note that these functions have nothing to do with the loading or interpretation of rueType data. The managers' functionalities should focus on the sole purpose of object management (allocation/sharing/caching/recycling). b. Using generic lists: The previous example has shown that we may not be able to know whether we'll need to track closely some structures or not. That's why I recommend the use of generic containers whenever possible. When putting objects in lists, either singly or doubly linked ones, one can either insert some link pointers within the objects, or use generic link elements. The latter solution is preferred, as it eases the extension of the library. Moreover, it becomes possible to use a single list manager, independently from the linked objects' types and functions. ______ ______ ______ | | | | | | -->| Next----->| Next----->| Next----->0 (NULL) | | | | | | | Data | | Data | | Data | |__|___| |__|___| |__|___| | | | | | | v v v __________ __________ __________ | | | | | | | Object | | Object | | Object | | | | | | | |__________| |__________| |__________| Example: Use of a generic list. The list is made of simple linked 'List_Element' structures, containing fields like a 'Next' link, and a 'Data' field used to point to the actual object. It is important that only the manager modifies or even parses list elements (this issue is critical for reentrant builds). The objects do not necessarily need a pointer to their list element (which could be added in the object's structure definitions, hough modified by the manager only). For example, these objects could be instance records, which already contain a pointer to their common resident record. The latter could then contain the head of the linked list. And finally it should be noted that we may introduce some additional fields into the list elements to hold some extra information, like flags or optional destructor functions pointers for the pointed objects etc. One should easily alternate between singly or doubly linked lists if required without touching anything else than the manager (and eventually the objects' type declaration to add or remove some fields). c. Add your own suggestions here... 2. Memory Allocation and Object Initialisation/Destruction: The data that is created and used to manage a specific domain concept (like a face, or an instance), is represented by a tree of objects. For example, the resident data is made of a root TResident_Record, which contains pointers to some other tables, which may in turn contain pointers to some sub-tables (like TResident_Record->CMap_Directory->CMap_Table). When we want to delete a face, we have to parse the tree in a depth-first order to delete all sub-tables, which means that destruction is not a trivial operation. One must know the structure and layout of the implemented hierarchy of objects to do it right. If we want to be able to extend the hierarchy easily, it is a good idea to isolate 'destructor' functions. Now, consider the fact that, as we may load a lot of information on-demand, some tables may, or may not, be present in memory. Consider also the case when we discover that a font file is broken, while loading one table and then must decide to destroy what was previously built. There are many ways to do that. Here is one: (Note: this is fictious code) Bool Load_Resident_Table( TT_Stream stream, PResident_Record* res ) { ... if ( !Load_TrueType_Directory( resident ) ) goto Error_1; if ( !Load_TrueType_Header( resident ) ) goto Error_2; if ( !Load_TrueType_MaxProfile( resident ) ) goto Error_3; if ( !Load_TrueType_CMaps( resident ) ) goto Error_4; ... // success, do the following work res = resident; return SUCCESS; Error_n: ... Error_5: Free_CMaps( resident ); Error_4: Free_MaxProfile( resident ); Error_3: Free_Header( resident ); Error_2: Free_Directory( resident ); Error_1: // nothing to free res = NULL; return FAILURE; } One can see that, in this example, allocations are 'unrolled' in the case of an error. Though this is elegant, it requires an additional function to destroy the resident data normally when a face's life-cycle ends. This means another routine, that should look like: void Free_Resident( PResident_Record res ) { .... Free_CMaps ( resident ); Free_MaxProfile( resident ); Free_Header ( resident ); Free_Directory ( resident ); } This means that we now have two iterations of a similar code. If we now decide to add a new table to the resident record, we'll have to add a call to its loader in 'Load_Resident_Table', and two calls to its destructor in both the loader and the destructor. That isn't really a good idea. Now imagine the case of more dynamic data, where some sub-tables may, or may not be there, depending on various and unpredictable factors (font file contents, user calls, etc.). This introduces some complexities in the destructor that are not necessarily duplicated in the loader. Now, we would have two different destruction schemes for the same data. This is still a bad thing. That's why I think that each table/structure that is not static needs a single destructor, that must be able to handle partially built data. Something that should look like: void Free_Resident( PResident_Record res ) { ... if ( res->cmaps_table ) { Free_CMaps( res->cmaps_table ); res->cmaps_table = NULL; res->numCMaps = 0; } if ( res->maxProfile ) { Free_MaxProfile( res->maxProfile ); res->maxProfile = NULL; } if ( res->fontHeader ) { Free_Header( res->fontHeader ); res->fontHeader = NULL; } ... } Using a simple convention: a NULL pointer indicates that the table isn't there. Otherwise, it should be destroyed, and other fields associated to the table should be set to 0 (like the 'res->numCMaps'). The Loader could also become simpler: { ... resident = New_Resident_Header(); // Get a new (fresh or recycled) resident header Init_Resident_Header( resident ); // Inits the resident header if ( ! Load_Table1( resident ) || // try to load the sub-tables ! Load_Table2( resident ) || ! Load_Table3( resident ) ) { // an error occured Free_Resident_Header( resident ); *res = NULL; return FAILURE; } // success *res = resident; return SUCCESS; } Here, we can see that: 1. We obtain the a new resident header through a function call (or a macro), which is better than using ALLOC or (malloc) directly. 2. We used a function 'Init_xx', that I would call a 'constructor' which main role is to clear all fields of the resident record, especially those that contain pointers. The constructor can also contain some other functionalities, like creating a new mutex for the object in a reentrant build. These are important tasks, but I don't think that they should be performed by the loader function directly. So the idea is to declare, for every table that might contain pointers to an owned subtable, several functions: - an Init_xxxxxx constructor, used to set all fields to 0 or NULL. The constructor can be a macro that casts a simple memset( table, sizeof( *table ), 0 ) But it's good to have the ability to change it for the sake of extensibility. In some cases, it's simply better to allocate and load the tables at the same time, in the same routine (that's what we're currently doing). If we decide to keep this technique for some of our functions, we'll need however a decent destructor... - a Free_xxxxx destructor, that should test the availability of each sub-table pointer before freeing them (this issue is important in the cases of partial and dynamic allocations). and possibly: - some life-cycle functions like New_xxxxx and Done_xxxxx that would allow later changes in the way we manage some of these tables. They are not a requirement for all tables but can be very useful. I think that the names of these functions are quite expressive, but we could also find some other ones. Talking about migration, I think it should be fairly easy to begin writing the Init_xxx and Free_xxx functions for our common non-static tables. That would probably be a great step in the right direction. I don't think we'll need to touch a lot of code. We already have some ALLOC macros that can be changed very easily to get rid of the growing heap. To be continued ...