EnvyMud release 1.0 Thursday, 30th June 1994 Kahn michael@uclink.berkeley.edu Thelonius dave@mechatro2.berkeley.edu Kith kith@marble.bu.edu Hatchet hatchet@uclink.berkeley.edu === Memory Management Overview Envy contains the following memory regions: run file memory; stack; string space; and permanent space. The approximate sizes of these regions are: Run file memory 832 k Stack 584 k String space 1390 k Permanent space 2234 k TOTAL 5040 k === Run File Memory The envy executable file has about 840k of code. This size is small compared to the total size, and there is little you can do to change it. === Stack We have never measured stack usage, but estimate it's somewhere between 580k and 600k. Envy has a wide, shallow calling tree. The largest consumers of stack memory are local buffers of size MAX_STRING_LENGTH. If you port Envy to a machine with 1024k or less of stack, you should instrument your object code with stack-usage measurements. Most compilers for machines in this range have an option to do this. === String Space and fread_string() At boot time, the function fread_string() is used to read in ~-delimited strings from area files. These strings are stored into string space. After all of the area files are read in, string space is read-only for the duration of the program. Duplicate strings are stored only once into string space; hashing is used to achieve this. The hash code for a string is simply its length. Each string in string space is prefaced with a backpointer to the previous string with the same hash code. (Aliasing through a union is needed to read and write these pointers, because they can start at any byte boundary, and thus are misaligned). When fread_string() reads a new string, it creates the string at the end of string space. It then finds the first hash pointer for that length and follows the thread of hash pointers, looking for an already existing string with the same contents. Strings in the hash chain are checked newest-first, which benefits from the usual construction of area files, where duplicates are usually duplicates of something seen recently. If fread_string() finds that the new string is a duplicate, it simply discards the new string and returns a pointer to the existing string. If the string is new, it leaves it at the end of string space, fills in the new hash pointers, and returns the new string. After area-file loading is over, fread_string is also used to read player files. In this case, new strings are not appended to string space, but instead are simply handed to str_dup(). Thus the amount of string space used is fixed at area-file loading time. The functions str_dup() and free_string() take advantage of string space. If a string being duplicated is in string space, str_dup() simply returns the same pointer. If a string being freed is in string space, free_string() simply does nothing. This strategy not only saves megabytes of memory through string re-use, but also saves processor time as well. Thus a cheap method is needed for deciding whether a given string is in string space. This is one reason why strings are stored in one contiguous region of size MAX_STRING. (The hash chains don't require contiguous allocation). Collecting all strings into one region has another advantage: locality of reference. Most strings are unused most of the time. Because they are not interspersed with other dynamically allocated memory, a virtual memory operating system can page out almost all of the string space without affecting performance. After boot time the unused end of string space is wasted. This amounts to about 110k in Envy 1.0. On a VM system this space is unused space is paged out quickly, so it doesn't hurt to leave it alone. However, you can recover this space easily by lowering MAX_STRING. If perchance you set MAX_STRING too low you will get a boot-time error, but never any operational errors. If you add a lot of areas you may need to increase MAX_STRING. Again, Envy will tell you when you've run out. === Permanent space This space holds everything else: all of the area file non-string data; all of the created mobiles and objects; descriptor and player character structures; you name it. This space is dynamically allocated from calloc() in large blocks, which are carved up and handed out as needed by alloc_perm(). As distributed, Envy 1.0 uses about 2234k of permanent space. Unlike string space, permanent space grows on demand; alloc_perm() calloc's and carves up as many blocks as needed as the game runs. You can adjust the block size by changing MAX_PERM_BLOCK in 'db.c'. Adjustment will have only a minor effect on space and time usage. If you port Envy to a new system with a 64k or 32k limit on calloc() size, you could simply change MAX_PERM_BLOCK to the largest calloc'able block on your system. Envy never calls free() to return memory. Instead, memory is recycled for future use. This has two advantages: it's faster to recycle a block than to call free(), and it's faster to allocate a block from a free list than to allocate one from calloc() or alloc_perm(). Most of the structure types have their own free lists: char_free, obj_free, affect_free, et cetera. Variable-sized blocks don't fit the per-structure-type free-list model. The functions alloc_mem() and free_mem() manage blocks of arbitrary size. They actually work by maintaining fixed-size lists for just a few supported sizes and rounding requests up to a supported size. This is extremely fast; because there are so few variable-sized blocks, the space penalty is inconsequential.