Selective collect

[tannewt]

In CircuitPython we're working on supporting our new Fruit Jam board. It uses HSTX to generate DVI video and PSRAM for a larger VM heap (via split heaps). One issue with our demos is that GC collect time gets long enough to chirp audio and stutter video. The heap grows significantly because we store bitmaps and audio buffers in the VM heap.

An idea I had to speed this up was to annotate which VM allocations need to be "collected" (aka scanning for heap pointers.) I've implemented this by adding another table like the one for finalisers. GC times dropped from 80+ms to ~25ms in our test example.

One question I struggled with is how to update the dozen or so memory allocation APIs. Some vary to allocate a struct or a variable length struct. Others vary depending on whether they should raise an error on failure, have a finaliser or zero memory. Now I'm adding a fourth boolean of whether the memory should be collected. What should the APIs be? Can we simplify things by splitting the size computation from the allocation policy?

Existing APIs

micropython/py/misc.h

Lines 70 to 115 in f498a16

	/** memory allocation ******************************************/
	// TODO make a lazy m_renew that can increase by a smaller amount than requested (but by at least 1 more element)
	#define m_new(type, num) ((type *)(m_malloc(sizeof(type) * (num))))
	#define m_new_maybe(type, num) ((type *)(m_malloc_maybe(sizeof(type) * (num))))
	#define m_new0(type, num) ((type *)(m_malloc0(sizeof(type) * (num))))
	#define m_new_obj(type) (m_new(type, 1))
	#define m_new_obj_maybe(type) (m_new_maybe(type, 1))
	#define m_new_obj_var(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
	#define m_new_obj_var0(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc0(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
	#define m_new_obj_var_maybe(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc_maybe(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
	#if MICROPY_MALLOC_USES_ALLOCATED_SIZE
	#define m_renew(type, ptr, old_num, new_num) ((type *)(m_realloc((ptr), sizeof(type) * (old_num), sizeof(type) * (new_num))))
	#define m_renew_maybe(type, ptr, old_num, new_num, allow_move) ((type *)(m_realloc_maybe((ptr), sizeof(type) * (old_num), sizeof(type) * (new_num), (allow_move))))
	#define m_del(type, ptr, num) m_free(ptr, sizeof(type) * (num))
	#define m_del_var(obj_type, var_field, var_type, var_num, ptr) (m_free(ptr, offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
	#else
	#define m_renew(type, ptr, old_num, new_num) ((type *)(m_realloc((ptr), sizeof(type) * (new_num))))
	#define m_renew_maybe(type, ptr, old_num, new_num, allow_move) ((type *)(m_realloc_maybe((ptr), sizeof(type) * (new_num), (allow_move))))
	#define m_del(type, ptr, num) ((void)(num), m_free(ptr))
	#define m_del_var(obj_type, var_field, var_type, var_num, ptr) ((void)(var_num), m_free(ptr))
	#endif
	#define m_del_obj(type, ptr) (m_del(type, ptr, 1))
	void *m_malloc(size_t num_bytes);
	void *m_malloc_maybe(size_t num_bytes);
	void *m_malloc_with_finaliser(size_t num_bytes);
	void *m_malloc0(size_t num_bytes);
	#if MICROPY_MALLOC_USES_ALLOCATED_SIZE
	void *m_realloc(void *ptr, size_t old_num_bytes, size_t new_num_bytes);
	void *m_realloc_maybe(void *ptr, size_t old_num_bytes, size_t new_num_bytes, bool allow_move);
	void m_free(void *ptr, size_t num_bytes);
	#else
	void *m_realloc(void *ptr, size_t new_num_bytes);
	void *m_realloc_maybe(void *ptr, size_t new_num_bytes, bool allow_move);
	void m_free(void *ptr);
	#endif
	NORETURN void m_malloc_fail(size_t num_bytes);
	#if MICROPY_TRACKED_ALLOC
	// These alloc/free functions track the pointers in a linked list so the GC does not reclaim
	// them. They can be used by code that requires traditional C malloc/free semantics.
	void *m_tracked_calloc(size_t nmemb, size_t size);
	void m_tracked_free(void *ptr_in);
	#endif

micropython/py/obj.h

Lines 922 to 936 in f498a16

	// Helper versions of m_new_obj when you need to immediately set base.type.
	// Implementing this as a call rather than inline saves 8 bytes per usage.
	#define mp_obj_malloc(struct_type, obj_type) ((struct_type *)mp_obj_malloc_helper(sizeof(struct_type), obj_type))
	#define mp_obj_malloc_var(struct_type, var_field, var_type, var_num, obj_type) ((struct_type *)mp_obj_malloc_helper(offsetof(struct_type, var_field) + sizeof(var_type) * (var_num), obj_type))
	void *mp_obj_malloc_helper(size_t num_bytes, const mp_obj_type_t *type);
	// Object allocation macros for allocating objects that have a finaliser.
	#if MICROPY_ENABLE_FINALISER
	#define mp_obj_malloc_with_finaliser(struct_type, obj_type) ((struct_type *)mp_obj_malloc_with_finaliser_helper(sizeof(struct_type), obj_type))
	#define mp_obj_malloc_var_with_finaliser(struct_type, var_type, var_num, obj_type) ((struct_type *)mp_obj_malloc_with_finaliser_helper(sizeof(struct_type) + sizeof(var_type) * (var_num), obj_type))
	void *mp_obj_malloc_with_finaliser_helper(size_t num_bytes, const mp_obj_type_t *type);
	#else
	#define mp_obj_malloc_with_finaliser(struct_type, obj_type) mp_obj_malloc(struct_type, obj_type)
	#define mp_obj_malloc_var_with_finaliser(struct_type, var_type, var_num, obj_type) mp_obj_malloc_var(struct_type, var_type, var_num, obj_type)
	#endif

Another approach would be to focus on the type of allocations being made. mp_obj_malloc is a good example of this. It makes it clear that the allocated memory is a Python object. Therefore it could have finaliser always set and always be collected.

How could we unify these allocation APIs to make them easier to maintain? Any ideas?

[jonnor]

Hi @tannewt - this is interesting work, especially as someone that does a bunch of work on C modules etc. I do not have any opinion on the API design at the moment, I would like to understand the intended usage a bit better first. What would be the typical cases where one would use this functionality, and how to decide if to use it or not. I guess any large allocation where the code that allocates knows there will not be any MP objects inside? And I guess the default behavior would have to be "do collection?", to maintain compatibility?

[tannewt]

I'm being more aggressive with it at the moment and making collection opt-in. I've made m_malloc and some m_new allocate without collection. mp_obj_malloc is collect by default because we know they are Python objects and likely have to be collected. (They are also likely small.) I've also add a m_malloc_items for things like tuple and list that have lists of Python object references.

You only need collection if you store a pointer to other VM heap allocated memory.

I mean to look at memory analysis tools (like valgrind) to see if we can use it to validate allocations.

[AJMansfield]

I'm being more aggressive with it at the moment and making collection opt-in.

This definitely should not be silently substituted for current mp_malloc behavior --- this would introduce bugs, and subtle hard-to-test-for ones at that. As a concrete example, since it's an area I've been recently working on:

In the implementation of PEP487 __set_name__ (#16806), it's necessary to accumulate a linked list of mp_call_method_n_kw argument arrays to avoid an edge-case iterate-while-modify hazard when invoking them. This setname_list_t is not a micropython object, but the remaining tail of this list must survive even across calls into user-provided python code. If the contents of the m_obj_new allocations used to append to this list were ignored by the garbage collector when determining reachability, that would make this a potential use-after-free.

It's not surprising that this case didn't rear its head when you swapped it out --- afaik, the only test in the suite that even could trigger this is tests/internal_bench/class_create-8.1-metaclass_setname5.py --- but it's not really a unique case either. Off-hand, I'm aware of at least one other similar bespoke linked list used for tracking VFS mountpoints, and there's probably others like it. And you'd need to really test extensively to find them: lists like these are happy-path optimizations, for making the data structures as close to free as possible for the majority cases. "Normal" code that doesn't e.g. allocate gobs of memory in its descriptors, or mount loads of filesystems, probably wouldn't even make these bugs register in valgrind.

[AJMansfield]

This sounds like a useful feature! IMO this should probably be made the default for the python-facing bytearray too, to defend against the possibility that a buffer full of maliciously-crafted data could suppress garbage collection entirely.

I think it would be better to call this weakdata rather than the more literal without_collect. "Weak" is a pretty standard term of art for "the garbage collector ignores this when determining reachability", and helps communicate the potential pitfalls of setting it better.

One question I struggled with is how to update the dozen or so memory allocation APIs. Some vary to allocate a struct or a variable length struct. Others vary depending on whether they should raise an error on failure, have a finaliser or zero memory. Now I'm adding a fourth boolean of whether the memory should be collected. What should the APIs be? Can we simplify things by splitting the size computation from the allocation policy?

I'm not quite familiar enough with the internals of how the GC's tables work to say for sure how easy this would be from a technical standpoint, but could this be implemented as its own entirely separate call? E.g:

ptr = mp_malloc(len);
mp_gc_weakdata(ptr, len);

Or even a more generic mp_madvise API that mirrors madvise from posix:

ptr = mp_malloc(len);
mp_madvise(ptr, len, MP_MADV_WEAKDATA);

That would also give an obvious place to put an implementation of gc.freeze() from BPO-31558.

How could we unify these allocation APIs to make them easier to maintain? Any ideas?

There are supposed to be code size advantages to having so many different allocation functions --- though I agree we should avoid proliferating even more versions of mp_i_hope_this_is_the_right_malloc.