The xml_allocator::deallocate_memory is NOT reentrant

[kevenkeller]

The xml_allocator::deallocate_memory is NOT reentrant, if called multiply time with same parameter ptr, page->freed_size += size will be executed multiply times, will cause page->freed_size > page->busy_size, the page will never deallocated. the memory will leaked.

[zeux]

The xml_allocator::deallocate_memory is NOT reentrant, if called multiply time with same parameter ptr

Freeing the same pointer multiple times is invalid.

[kevenkeller]

I fix the bug as follow:
1.
static const uintptr_t xml_memory_block_contents_freed = 0x01;

struct xml_memory_block_header
{
	uint16_t block_mask; // block mask
	uint16_t unused[3]; // unused
	xml_memory_block_header()
	{
		block_mask = 0;
		unused[0] = unused[1] = unused[2] = 0;
	}
};

2
In method xml_allocator::allocate_memory, change code

if (PUGI_IMPL_UNLIKELY(_busy_size + size + sizeof(xml_memory_block_header) > xml_memory_page_size))
return allocate_memory_oob(size, out_page);

char* buf = reinterpret_cast<char*>(_root) + sizeof(xml_memory_page) + _busy_size;

xml_memory_block_header* header = new (buf) xml_memory_block_header();//reinterpret_cast<xml_memory_block_header*>(buf);
/*header->block_mask = 0;
header->unused[0] = header->unused[1] = header->unused[2] = 0;*/

_busy_size += size + sizeof(xml_memory_block_header);
buf += sizeof(xml_memory_block_header);
out_page = _root;
return reinterpret_cast<char*>(buf);

3
In method xml_allocator::allocate_memory_oob, change code

const size_t large_allocation_threshold = xml_memory_page_size / 4;
xml_memory_page* page = allocate_page(size + sizeof(xml_memory_block_header) <= large_allocation_threshold ? xml_memory_page_size : size + sizeof(xml_memory_block_header));
out_page = page;

if (!page) return 0;

if (size <= large_allocation_threshold)
{
	_root->busy_size = _busy_size;

	// insert page at the end of linked list
	page->prev = _root;
	_root->next = page;
	_root = page;

	_busy_size = size + sizeof(xml_memory_block_header);
}
else
{
	// insert page before the end of linked list, so that it is deleted as soon as possible
	// the last page is not deleted even if it's empty (see deallocate_memory)
	assert(_root->prev);

	page->prev = _root->prev;
	page->next = _root;

	_root->prev->next = page;
	_root->prev = page;

	page->busy_size = size + sizeof(xml_memory_block_header);
#ifdef TEST
	char* buf = reinterpret_cast<char*>(page) + sizeof(xml_memory_page) + sizeof(xml_memory_block_header);
	page->busys->push_back(std::shared_ptr<xml_memory_page::mem_op>(new xml_memory_page::mem_op(size, buf)));
#endif
}
char* buf = reinterpret_cast<char*>(page) + sizeof(xml_memory_page);
xml_memory_block_header* header = new (buf) xml_memory_block_header();// reinterpret_cast<xml_memory_block_header*>(buf);
buf += sizeof(xml_memory_block_header);
return buf;

4 In method xml_allocator::deallocate_memory, change code

if (page == _root) page->busy_size = _busy_size;

assert(ptr >= reinterpret_cast<char*>(page) + sizeof(xml_memory_page) +sizeof(xml_memory_block_header) && ptr < reinterpret_cast<char*>(page) + sizeof(xml_memory_page) + page->busy_size);
(void)!ptr;

xml_memory_block_header* header = reinterpret_cast<xml_memory_block_header*>(reinterpret_cast<char*>(ptr) - sizeof(xml_memory_block_header));
if ((header->block_mask & xml_memory_block_contents_freed) == xml_memory_block_contents_freed)
{
	return;
}
header->block_mask |= xml_memory_block_contents_freed;
page->freed_size += size + sizeof(xml_memory_block_header);
assert(page->freed_size <= page->busy_size);

...

[kevenkeller]

The xml_allocator::deallocate_memory is NOT reentrant, if called multiply time with same parameter ptr

Freeing the same pointer multiple times is invalid.

If a removed xml_node instance be removed multple times will cause deallocate_memory be called multiply times.

[zeux]

If a removed xml_node instance be removed multple times will cause deallocate_memory be called multiply times.

First, this is invalid code; it's somewhat similar to double-free or double-delete in C++. Quoting pugixml manual:

Once underlying node/attribute objects are destroyed, the handles to those objects become invalid. While this means that destruction of the entire tree invalidates all node/attribute handles, it also means that destroying a subtree (by calling xml_node::remove_child) or removing an attribute invalidates the corresponding handles

Second, attempting to do this will generally speaking cleanly fail (remove_child will return false) because the removed node will be unparented from the tree. I'm not sure how exactly you are reproducing this. If the node memory gets reused by subsequent allocations then all bets are off of course.

[kevenkeller]

If a removed xml_node instance be removed multple times will cause deallocate_memory be called multiply times.

First, this is invalid code; it's somewhat similar to double-free or double-delete in C++. Quoting pugixml manual:

Once underlying node/attribute objects are destroyed, the handles to those objects become invalid. While this means that destruction of the entire tree invalidates all node/attribute handles, it also means that destroying a subtree (by calling xml_node::remove_child) or removing an attribute invalidates the corresponding handles

Second, attempting to do this will generally speaking cleanly fail (remove_child will return false) because the removed node will be unparented from the tree. I'm not sure how exactly you are reproducing this. If the node memory gets reused by subsequent allocations then all bets are off of course.

A removed xml_node instance named _node.
`_node.text().set(L"")``
the code will call impl::strcpy_insitu with parameter (source_length=0) , in the method

if (source_length == 0)
{
	// empty string and null pointer are equivalent, so just deallocate old memory
	xml_allocator* alloc = PUGI_IMPL_GETPAGE_IMPL(header)->allocator;

	**if (header & header_mask) alloc->deallocate_string(dest);**

	// mark the string as not allocated
	dest = 0;
	header &= ~header_mask;

	return true;
}

call deallocate_string will cause call deallocate_memory and the memory leaked.

[zeux]

Ah, yeah, the internal structure of nodes is not cleared in some cases after removal to improve performance of destroying large trees. Again, all of the operations on removed nodes are invalid; this is use after free.

If you want to get better diagnostics for the case above I think you can try to change destroy_node to do this n->header &= ~xml_memory_page_type_mask; before the call to deallocate_memory (which will cause most future operations on node to fail... but again, this is only until the space used by the node is reclaimed by something else! use-after-free is inherently a bug in the program).