worley@EDDIE.MIT.EDU (Dale Worley) (10/26/89)
Gnu Emacs uses memory in a dynamically allocated manner. Memory tends to be allocated in small chunks (list cells, small strings) and in large chunks (buffers, large strings). (To prevent various problems, small chunks are suballocated out of large chunks that are reserved for this purpose.) Memory becomes free in more-or-less random order, so the memory space tends to be a mosaic of free and in-use areas. Most Unix systems allow the user to change his memory allocation only by enlarging or shrinking the data area, and then only by moving the high-address end. However, the high-address end of the data area is likely to be a mosaic of free and in-use areas, and so it is very unlikely that its end can be moved down by much at any time, even if a large fraction of the data area is free. Thus, there is no utility in designing a mechanism to detect and free memory from the address space. (If the kernel provided a mechanism to free interior parts of the data area address space, it might be worthwhile for Emacs to deallocate large free chunks.) The traditional solution to such problems is called 'compactification' -- moving all in-use data areas into a compact mass at the low end of the data area, and then deallocating the huge free area left at the high end. To do this successfully requires that all pointers to any data area be altered to point to the new addresses, which (despite some earlier speculations of mine) requires much careful design and is very error-prone. Dale Worley Compass, Inc. worley@compass.com -- All through human history, tyrannies have tried to enforce obedience by prohibiting disrespect for the symbols of their power. The swastika is only one example of many in recent history. -- American Bar Association task force on flag burning
mac@rhea.ardent.com (Mike McNamara) (10/31/89)
In article <8910261557.AA02573@sn1987a.compass.com> compass!worley@EDDIE.MIT.EDU (Dale Worley) writes: > The traditional solution to such problems is called 'compactification' > -- moving all in-use data areas into a compact mass at the low end of > the data area, and then deallocating the huge free area left at the > high end. To do this successfully requires that all pointers to any > data area be altered to point to the new addresses, which (despite > some earlier speculations of mine) requires much careful design and is > very error-prone. Could you just add one level of indirection to the memory allocation scheme? ie. define a new malloc to be char ** gc_malloc(unsigned int); instead of char * malloc(unsigned int); You also need a gc_lock(char**); and gc_unlock(char**), which allow modules to temporarily gain protection for a dereferenced pointer. [Perhaps this is what you mean by careful design and error prone.] You slowly migrate the potentially large memory allocators to this scheme. I have programmed a number of PC's which used the above scheme to manage memory. Then when compactifing, you simply deal with those of your internal list of char*s which are not currently gc_lock'ed. At the expense of an additional dereference for every pointer usage (non trivial, yes, but 32MHz is pretty fast..), this allows simple, save memory compactification. > > Dale Worley Compass, Inc. worley@compass.com > --
mac%rhea@EDDIE.MIT.EDU (Mike McNamara) (10/31/89)
In article <8910261557.AA02573@sn1987a.compass.com> compass!worley@EDDIE.MIT.EDU (Dale Worley) writes: > The traditional solution to such problems is called 'compactification' > -- moving all in-use data areas into a compact mass at the low end of > the data area, and then deallocating the huge free area left at the > high end. To do this successfully requires that all pointers to any > data area be altered to point to the new addresses, which (despite > some earlier speculations of mine) requires much careful design and is > very error-prone. Could you just add one level of indirection to the memory allocation scheme? ie. define a new malloc to be char ** gc_malloc(unsigned int); instead of char * malloc(unsigned int); You also need a gc_lock(char**); and gc_unlock(char**), which allow modules to temporarily gain protection for a dereferenced pointer. [Perhaps this is what you mean by careful design and error prone.] You slowly migrate the potentially large memory allocators to this scheme. I have programmed a number of PC's which used the above scheme to manage memory. Then when compactifing, you simply deal with those of your internal list of char*s which are not currently gc_lock'ed. At the expense of an additional dereference for every pointer usage (non trivial, yes, but 32MHz is pretty fast..), this allows simple, save memory compactification. > > Dale Worley Compass, Inc. worley@compass.com > -- Michael McNamara (St)ardent, Inc. mac@ardent.com --