Thread: Aligning memory

  1. #1
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839

    Aligning memory

    So I managed to get my custom allocation function working (I think) but now I'm running into an issue where the last detected function is __memset_sse2_unaligned_erms before a segfault which made me adjust the integer types to just uintptr_t and the rest are just pointers, I even went as far as to change the page allocation code to use additional variables to ensure the page is aligned to sizeof(void*) but even that did not fix the issue, I'm starting to consider just replacing the pointers with uintptr_t in case the compiler is using smaller than expected pointers, any ideas in case that's not it?

  2. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,736
    Is this related to the Lua stack? If so, then it can be a bit weird in my experience. Write a small test case that exhibits the problem so that we can compile and test

  3. #3
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    No, took me a few tries to get a copy past code to run (idiot that I am I forgot to add a run command after compiling) but here's the resulting file without lua and glut, didn't prune the headers beyond that.
    Code:
    #include <inttypes.h>
    #include <sys/types.h>
    #include <errno.h>
    #include <ctype.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <dirent.h>
    
    #include <string.h>
    #include <sys/mman.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    int fail() {
    	printf("Error 0x%08X %s", errno, strerror(errno) );
    	return EXIT_FAILURE;
    }
    
    void foo_atexit() {
    	(void)fail();
    }
    
    typedef unsigned char uchar;
    
    typedef struct foo_addr {
    	uintptr_t size;
    	void *page, *data;
    	struct foo_addr *next, *prev;
    } foo_addr_t;
    typedef struct foo_page {
    	uintptr_t size, left;
    	uchar *base, *data, *stop;
    	struct foo_addr * root, *last;
    } foo_page_t;
    size_t pages_size = 0, pages_want = 0;
    size_t pages_used = 0, pages_upto = 0, pages_node = 0;
    foo_page_t* pages;
    int page_fd = -1;
    int foo_find_addr_in_pages( void *ptr, foo_page_t **dst, foo_addr_t **pos ) {
    	size_t p = 0;
    	foo_page_t *page;
    	foo_addr_t *addr;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	if ( !ptr ) return EXIT_FAILURE;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		for ( addr = page->root; addr; addr = addr->next ) {
    			if ( addr->data == ptr ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    			if ( addr == page->last ) break;
    		}
    	}
    	return EINVAL;
    }
    int foo_try_page_addr(
    	foo_page_t *page, foo_addr_t *addr, size_t want ) {
    	foo_addr_t *next = NULL;
    	size_t size;
    	if ( !page || !addr ) return EDESTADDRREQ;
    	if ( (size = want % sizeof(void*)) )
    		want += sizeof(void*) - size;
    	if ( next ) {
    		for ( next = addr->next; addr->size < want; next = next->next ) {
    			if ( next->data ) return ENOMEM;
    			addr->size += (next->size + sizeof(foo_addr_t));
    			if ( next == page->last ) {
    				next = NULL;
    				page->last = addr;
    				break;
    			}
    			addr->next = next->next;
    		}
    	}
    	addr->next = next;
    	if ( addr->size < want ) return ENOMEM;
    	addr->data = (uchar*)(addr + sizeof(foo_addr_t));
    	if ( addr->size > want ) {
    		if ( addr->size - want > sizeof(foo_addr_t) ) {
    			next = (foo_addr_t*)((uintptr_t)(addr->data) + want);
    			if ( (void*)next >= (void*)
    				((uintptr_t)(page->stop) - (sizeof(foo_addr_t) + 1)) )
    				return EXIT_SUCCESS;
    			next->next = addr->next;
    			next->prev = addr;
    			addr->next = next;
    			next->size = (addr->size - want) - sizeof(foo_addr_t);
    			next->data = (void*)((uintptr_t)next + sizeof(foo_addr_t));
    			addr->size = want;
    			if ( page->last == addr ) page->last = next;
    		}
    	}
    	return EXIT_SUCCESS;
    }
    int foo_find_memory(
    	foo_page_t **base, foo_addr_t **dst, size_t want )
    {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL;
    	size_t p;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		addr = page->root;
    		while ( addr ) {
    			if ( foo_try_page_addr( page, addr, want ) == EXIT_SUCCESS ) {
    				*base = page;
    				*dst = addr;
    				return EXIT_SUCCESS;
    			}
    			addr = addr->next;
    		}
    	}
    	if ( pages_used == pages_upto ) {
    		pages_want = sizeof(foo_page_t) * (pages_used + 100);
    		page = (foo_page_t*)realloc((void*)pages, pages_want);
    		if ( !page ) return ENOMEM;
    		pages = page;
    		pages_upto += 100;
    		pages_size = pages_want;
    	}
    	page = &(pages[p]);
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= (want / page->size)+1;
    	if ( page_fd < 0 ) {
    		page_fd = open("/dev/zero", O_RDWR);
    		if ( page_fd < 0 ) return errno;
    	}
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	if ( !(page->data) || page->data == (uchar*)-1 ) return errno;
    	++pages_used;
    	page->stop = (page->base + page->size);
    	if ( (p = (uintptr_t)(page->base) % sizeof(void*)) ) {
    		page->data = page->base + p;
    		page->left = page->size - p;
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	addr = page->last = page->root =
    		(foo_addr_t*)(memset( page->data, 0, page->left ));
    	addr->size = page->left - sizeof(foo_addr_t);
    	addr->next = page->last;
    	addr->data = NULL;
    	(void)foo_try_page_addr( page, addr, want );
    	*base = page;
    	*dst = addr;
    	return EXIT_SUCCESS;
    }
    int foo__alloc( void **dst, size_t want ) {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *current = NULL;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( !want ) {
    		if ((errno = foo_find_addr_in_pages( *dst, &page, &addr ))
    			!= EXIT_SUCCESS)
    			return errno;
    		*dst = NULL;
    		addr->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( *dst ) {
    		if ((errno = foo_find_addr_in_pages(*dst,&page,&current))
    			!= EXIT_SUCCESS)
    			return errno;
    		if ( foo_try_page_addr( page, current, want )
    			== EXIT_SUCCESS )
    			return EXIT_SUCCESS;
    		if ( (errno = foo_find_memory( &page, &addr, want ))
    			!= EXIT_SUCCESS )
    			return errno;
    		*dst = memcpy( addr->data, current->data, current->size );
    		current->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( (errno = foo_find_memory( &page, &addr, want ))
    		!= EXIT_SUCCESS )
    		return errno;
    	foo_try_page_addr( page, addr, want );
    	return EXIT_SUCCESS;
    }
    void foo__freeall() {
    	size_t p;
    	for ( p = 0; p < pages_used; ++p )
    		munmap( pages[p].base, sysconf(_SC_PAGESIZE) );
    	free(pages);
    	pages = NULL;
    	pages_used = pages_upto = 0;
    	pages_size = pages_want = 0;
    	if ( page_fd >= 0 )
    		close(page_fd);
    }
    void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
    	uchar *tmp = ptr;
    	(void)ud;
    	if ( (errno = foo__alloc( (void**)(&tmp), want ))
    		!= EXIT_SUCCESS )
    		goto nomem;
    	if ( !ptr ) memset( tmp, 0, want );
    	if ( size < want ) memset( &tmp[size], 0, want - size );
    	return tmp;
    	nomem:
    	if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
    	return NULL;
    }
    int main( int argc, char *argv[] ) {
    	size_t size = 8096;
    	char *buff = NULL;
    	atexit(foo_atexit);
    	puts(argv[0]);
    	if ( !(buff = foo_alloc(NULL,buff,0,size)) )
    		return fail();
    	if (!buff) return fail();
    	memset(buff,0,size);
    	strcpy( buff, "Hello World!\n" );
    	puts( buff );
    	foo_alloc( NULL, buff, size, 0 );
    	foo__freeall();
    	return EXIT_SUCCESS;
    }
    The line the debugger see before the segfault always contains an attempt to call memset, probably do the same for memcpy but doesn't get the chance

  4. #4
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Well I found I missed setting the destination pointer with the aquired memory so I fixed that but now I get segfault there instead, also I was starting to find the names of my functions confusing a bit so I renamed them to names I think are clearer:
    Code:
    #include <inttypes.h>
    #include <sys/types.h>
    #include <errno.h>
    #include <ctype.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <dirent.h>
    
    #include <string.h>
    #include <sys/mman.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    int fail() {
    	printf("Error 0x%08X %s", errno, strerror(errno) );
    	return EXIT_FAILURE;
    }
    
    void foo_atexit() {
    	(void)fail();
    }
    
    typedef unsigned char uchar;
    
    typedef struct foo_addr {
    	uintptr_t size;
    	void *page, *data;
    	struct foo_addr *next, *prev;
    } foo_addr_t;
    typedef struct foo_page {
    	uintptr_t size, left;
    	uchar *base, *data, *stop;
    	struct foo_addr * root, *last;
    } foo_page_t;
    size_t pages_size = 0, pages_want = 0;
    size_t pages_used = 0, pages_upto = 0, pages_node = 0;
    foo_page_t* pages;
    int page_fd = -1;
    int foo__has_addr(
    	foo_page_t **dst, foo_addr_t **pos, void *ptr ) {
    	size_t p = 0;
    	foo_page_t *page;
    	foo_addr_t *addr;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	if ( !ptr ) return EXIT_FAILURE;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		for ( addr = page->root; addr; addr = addr->next ) {
    			if ( addr->data == ptr ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    			if ( addr == page->last ) break;
    		}
    	}
    	return EINVAL;
    }
    int foo__try_addr(
    	foo_page_t *page, foo_addr_t *addr, size_t want ) {
    	foo_addr_t *next = NULL;
    	size_t size;
    	if ( !page || !addr ) return EDESTADDRREQ;
    	if ( (size = want % sizeof(void*)) )
    		want += sizeof(void*) - size;
    	if ( (next = addr->next) ) {
    		for ( next = addr->next; addr->size < want; next = next->next ) {
    			if ( next->data ) return ENOMEM;
    			addr->size += (next->size + sizeof(foo_addr_t));
    			if ( next == page->last ) {
    				next = NULL;
    				page->last = addr;
    				break;
    			}
    			addr->next = next->next;
    		}
    	}
    	addr->next = next;
    	if ( addr->size < want ) return ENOMEM;
    	addr->data = (uchar*)(addr + sizeof(foo_addr_t));
    	if ( !next && addr->size > want ) {
    		if ( addr->size - want > sizeof(foo_addr_t) ) {
    			next = (foo_addr_t*)((uintptr_t)(addr->data) + want);
    			if ( (void*)next >= (void*)
    				((uintptr_t)(page->stop) - (sizeof(foo_addr_t) + 1)) )
    				return EXIT_SUCCESS;
    			next->next = addr->next;
    			next->prev = addr;
    			addr->next = next;
    			next->size = (addr->size - want) - sizeof(foo_addr_t);
    			next->data = (void*)((uintptr_t)next + sizeof(foo_addr_t));
    			addr->size = want;
    			if ( page->last == addr ) page->last = next;
    		}
    	}
    	return EXIT_SUCCESS;
    }
    int foo__new_addr(
    	foo_page_t **base, foo_addr_t **dst, size_t want )
    {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL;
    	size_t p;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		addr = page->root;
    		while ( addr ) {
    			if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS ) {
    				*base = page;
    				*dst = addr;
    				return EXIT_SUCCESS;
    			}
    			addr = addr->next;
    		}
    	}
    	if ( pages_used == pages_upto ) {
    		pages_want = sizeof(foo_page_t) * (pages_used + 100);
    		page = (foo_page_t*)realloc((void*)pages, pages_want);
    		if ( !page ) return ENOMEM;
    		pages = page;
    		pages_upto += 100;
    		pages_size = pages_want;
    	}
    	page = &(pages[p]);
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= (want / page->size)+1;
    	if ( page_fd < 0 ) {
    		page_fd = open("/dev/zero", O_RDWR);
    		if ( page_fd < 0 ) return errno;
    	}
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	if ( !(page->data) || page->data == (uchar*)-1 ) return errno;
    	++pages_used;
    	page->stop = (page->base + page->size);
    	if ( (p = (uintptr_t)(page->base) % sizeof(void*)) ) {
    		page->data = page->base + p;
    		page->left = page->size - p;
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	addr = page->last = page->root =
    		(foo_addr_t*)(memset( page->data, 0, page->left ));
    	addr->size = page->left - sizeof(foo_addr_t);
    	addr->next = page->last;
    	addr->data = NULL;
    	(void)foo__try_addr( page, addr, want );
    	*base = page;
    	*dst = addr;
    	return EXIT_SUCCESS;
    }
    int foo__alloc( void **dst, size_t want ) {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *prev = NULL;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( !want ) {
    		if ((errno = foo__has_addr( &page, &addr, *dst ))
    			!= EXIT_SUCCESS)
    			return errno;
    		*dst = NULL;
    		addr->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( *dst ) {
    		if ((errno = foo__has_addr(&page,&prev,*dst))
    			!= EXIT_SUCCESS)
    			return errno;
    		if ( foo__try_addr( page, prev, want ) == EXIT_SUCCESS )
    			return EXIT_SUCCESS;
    		if ( (errno = foo__new_addr( &page, &addr, want ))
    			!= EXIT_SUCCESS )
    			return errno;
    		*dst = memcpy( addr->data, prev->data, prev->size );
    		prev->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( (errno = foo__new_addr( &page, &addr, want ))
    		!= EXIT_SUCCESS )
    		return errno;
    	(void)foo__try_addr( page, addr, want );
    	*dst = addr->data; // Crashes here
    	return EXIT_SUCCESS;
    }
    void foo__freeall() {
    	size_t p;
    	for ( p = 0; p < pages_used; ++p )
    		munmap( pages[p].base, sysconf(_SC_PAGESIZE) );
    	free(pages);
    	pages = NULL;
    	pages_used = pages_upto = 0;
    	pages_size = pages_want = 0;
    	if ( page_fd >= 0 ) close(page_fd);
    }
    void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
    	uchar *tmp = ptr;
    	(void)ud;
    	if ( (errno = foo__alloc( (void**)(&tmp), want ))
    		!= EXIT_SUCCESS )
    		return NULL;
    	if ( !want ) return NULL;
    	if ( !ptr || !size ) memset( tmp, 0, want );
    	if ( size < want ) memset( &tmp[size], 0, want - size );
    	return tmp;
    }
    int main( int argc, char *argv[] ) {
    	size_t size = 8096;
    	char *buff = NULL;
    	atexit(foo_atexit);
    	puts("Allocating memory...");
    	if ( !(buff = foo_alloc(NULL,buff,0,size)) )
    		return fail();
    	puts("Clearing memory...");
    	memset(buff,0,size);
    	puts("Filling memory...");
    	strcpy( buff, "Hello World!\n" );
    	puts( buff );
    	puts("Releasing memory...");
    	foo_alloc( NULL, buff, size, 0 );
    	foo__freeall();
    	return EXIT_SUCCESS;
    }
    Just look for '// Crashes here'

  5. #5
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    So I stopped ignoring the results of certain functions to check where the error is 1st caught and narrowed down the source of the problem to this function:
    Code:
    int foo__new_addr(
    	foo_page_t **dst, foo_addr_t **pos, size_t want )
    {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	size_t p;
    	*dst = NULL;
    	*pos = NULL;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		addr = page->root;
    		while ( addr ) {
    			if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    			addr = addr->next;
    		}
    	}
    	if ( pages_used == pages_upto ) {
    		pages_want = sizeof(foo_page_t) * (pages_used + 100);
    		page = (foo_page_t*)realloc((void*)pages, pages_want);
    		if ( !page ) return ENOMEM;
    		pages = page;
    		pages_upto += 100;
    		pages_size = pages_want;
    	}
    	page = &(pages[p]);
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= (want / page->size)+1;
    	if ( page_fd < 0 ) {
    		page_fd = open("/dev/zero", O_RDWR);
    		if ( page_fd < 0 ) {
    			if (errno == EXIT_SUCCESS) errno = EXIT_FAILURE;
    			return errno;
    		}
    	}
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	if ( !(page->data) || page->data == (uchar*)-1 ) return errno;
    	++pages_used;
    	page->stop = (page->base + page->size);
    	if ( (p = (uintptr_t)(page->base) % sizeof(void*)) ) {
    		page->data = page->base + p;
    		page->left = page->size - p;
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	addr = page->last = page->root =
    		(foo_addr_t*)(memset( page->data, 0, page->left ));
    	addr->size = page->left - sizeof(foo_addr_t);
    	addr->next = page->last;
    	addr->data = NULL;
    	if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    		return errno;
    	*dst = page;
    	*pos = addr;
    	return EXIT_SUCCESS;
    }
    Somehow dst & pos are not being set when it returns EXIT_SUCCESS somewhere

  6. #6
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Well I fixed another bug and the test program started working fine straight after that, the bug was that I was comparing against the wrong value (page->data instead of page->base), a bug introduced when I was trying to align my memory. Now the oddity is that while it runs fine when NOT debugging, it chokes at memset when I'm debugging it, still same issue, memory not aligned.
    I'll start with the output this time 1st:
    Code:
    make --no-print-directory alloc
    clang -ggdb -fPIC -fpic -llua -o alloc.elf alloc.c
    ./alloc.elf
    Allocating memory...
    foo__try_addr(2) page = 0x55ad005712b0, addr = 0x7f89f429b000, want = 8096
    foo__new_addr(2) page = 0x55ad005712b0, addr = 0x7f89f429b000, want = 8096
    foo__alloc(3) page = 0x55ad005712b0, addr = 0x7f89f429b000, want = 8096
    foo__try_addr(2) page = 0x55ad005712b0, addr = 0x7f89f429b000, want = 8096
    Clearing memory...
    Filling memory...
    Hello World!
    Releasing memory...
    foo__has_addr() page = 0x55ad005712b0, addr = 0x7f89f429b000
    Error 0x00000000 Success
    gede --args ./alloc.elf
    27.441| INFO  | Using: /dev/pts/2
    27.508| INFO  | Found ctags ('ctags')
    Compilation finished successfully.
    Code:
    #include <inttypes.h>
    #include <sys/types.h>
    #include <errno.h>
    #include <ctype.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <dirent.h>
    
    #include <string.h>
    #include <sys/mman.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    int fail() {
    	printf("Error 0x%08X %s\n", errno, strerror(errno) );
    	return EXIT_FAILURE;
    }
    
    void foo_atexit() {
    	(void)fail();
    }
    
    typedef unsigned char uchar;
    
    typedef struct foo_addr {
    	uintptr_t size;
    	void *page, *data;
    	struct foo_addr *next, *prev;
    } foo_addr_t;
    typedef struct foo_page {
    	uintptr_t size, left;
    	uchar *base, *data, *stop;
    	struct foo_addr * root, *last;
    } foo_page_t;
    size_t pages_size = 0, pages_want = 0;
    size_t pages_used = 0, pages_upto = 0, pages_node = 0;
    foo_page_t* pages;
    int page_fd = -1;
    int foo__has_addr(
    	foo_page_t **dst, foo_addr_t **pos, void *ptr ) {
    	size_t p = 0;
    	foo_page_t *page;
    	foo_addr_t *addr;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	if ( !ptr ) return EXIT_FAILURE;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		for ( addr = page->root; addr; addr = addr->next ) {
    			if ( addr->data == ptr ) {
    				*dst = page;
    				*pos = addr;
    				printf("%s() page = %p, addr = %p\n", __func__, page, addr );
    				return EXIT_SUCCESS;
    			}
    			if ( addr == page->last ) break;
    		}
    	}
    	return EINVAL;
    }
    int foo__try_addr(
    	foo_page_t *page, foo_addr_t *addr, size_t want ) {
    	foo_addr_t *next = NULL;
    	size_t size;
    	if ( !page || !addr ) return EDESTADDRREQ;
    	if ( (size = want % sizeof(void*)) )
    		want += sizeof(void*) - size;
    	if ( (next = addr->next) ) {
    		for ( next = addr->next; addr->size < want; next = next->next ) {
    			if ( next->data ) return ENOMEM;
    			addr->size += (next->size + sizeof(foo_addr_t));
    			if ( next == page->last ) {
    				next = NULL;
    				page->last = addr;
    				break;
    			}
    			addr->next = next->next;
    		}
    	}
    	addr->next = next;
    	if ( addr->size < want ) return ENOMEM;
    	addr->data = (uchar*)(addr + sizeof(foo_addr_t));
    	if ( !next && addr->size > want ) {
    		if ( addr->size - want > sizeof(foo_addr_t) ) {
    			next = (foo_addr_t*)((uintptr_t)(addr->data) + want);
    			if ( (void*)next >= (void*)
    				((uintptr_t)(page->stop) - (sizeof(foo_addr_t) + 1)) ) {
    				printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    				return EXIT_SUCCESS;
    			}
    			next->next = addr->next;
    			next->prev = addr;
    			addr->next = next;
    			next->size = (addr->size - want) - sizeof(foo_addr_t);
    			next->data = (void*)((uintptr_t)next + sizeof(foo_addr_t));
    			addr->size = want;
    			if ( page->last == addr ) page->last = next;
    		}
    	}
    	printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    	return EXIT_SUCCESS;
    }
    int foo__new_addr(
    	foo_page_t **dst, foo_addr_t **pos, size_t want )
    {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	size_t p;
    	*dst = NULL;
    	*pos = NULL;
    	for ( p = 0; p < pages_used; ++p ) {
    		page = &(pages[p]);
    		addr = page->root;
    		while ( addr ) {
    			if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS ) {
    				*dst = page;
    				*pos = addr;
    				printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    				return EXIT_SUCCESS;
    			}
    			addr = addr->next;
    		}
    	}
    	if ( pages_used == pages_upto ) {
    		pages_want = sizeof(foo_page_t) * (pages_used + 100);
    		page = (foo_page_t*)realloc((void*)pages, pages_want);
    		if ( !page ) {
    			if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
    			return errno;
    		}
    		pages = page;
    		pages_upto += 100;
    		pages_size = pages_want;
    	}
    	page = &(pages[p]);
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= (want / page->size)+1;
    	if ( page_fd < 0 ) {
    		page_fd = open("/dev/zero", O_RDWR);
    		if ( page_fd < 0 ) {
    			if (errno == EXIT_SUCCESS) errno = EXIT_FAILURE;
    			return errno;
    		}
    	}
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	if ( !(page->base) || page->base == (uchar*)-1 ) {
    		if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
    		return errno;
    	}
    	++pages_used;
    	page->stop = (page->base + page->size);
    	if ( (p = (uintptr_t)(page->base) % sizeof(void*)) ) {
    		page->data = page->base + p;
    		page->left = page->size - p;
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	addr = page->last = page->root =
    		(foo_addr_t*)(memset( page->data, 0, page->left ));
    	addr->size = page->left - sizeof(foo_addr_t);
    	addr->next = page->last;
    	addr->data = NULL;
    	if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    		return errno;
    	*dst = page;
    	*pos = addr;
    	printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    	return EXIT_SUCCESS;
    }
    int foo__alloc( void **dst, size_t want ) {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *prev = NULL;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( !want ) {
    		if ((errno = foo__has_addr( &page, &addr, *dst ))
    			!= EXIT_SUCCESS)
    			return errno;
    		*dst = NULL;
    		addr->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( *dst ) {
    		if ((errno = foo__has_addr(&page,&prev,*dst))
    			!= EXIT_SUCCESS)
    			return errno;
    		if ( foo__try_addr( page, prev, want ) == EXIT_SUCCESS ) {
    			printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    			return EXIT_SUCCESS;
    		}
    		if ( (errno = foo__new_addr( &page, &addr, want ))
    			!= EXIT_SUCCESS )
    			return errno;
    		printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    		*dst = memcpy( addr->data, prev->data, prev->size );
    		prev->data = NULL;
    		return EXIT_SUCCESS;
    	}
    	if ( (errno = foo__new_addr( &page, &addr, want ))
    		!= EXIT_SUCCESS )
    		return errno;
    	printf("%s(3) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
    	if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    		return errno;
    	*dst = addr->data;
    	return EXIT_SUCCESS;
    }
    void foo__freeall() {
    	size_t p;
    	for ( p = 0; p < pages_used; ++p )
    		munmap( pages[p].base, sysconf(_SC_PAGESIZE) );
    	free(pages);
    	pages = NULL;
    	pages_used = pages_upto = 0;
    	pages_size = pages_want = 0;
    	if ( page_fd >= 0 ) close(page_fd);
    }
    void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
    	uchar *tmp = ptr;
    	(void)ud;
    	if ( (errno = foo__alloc( (void**)(&tmp), want ))
    		!= EXIT_SUCCESS )
    		return NULL;
    	if ( !want ) return NULL;
    	if ( !ptr || !size ) memset( tmp, 0, want );
    	if ( size < want ) memset( &tmp[size], 0, want - size );
    	return tmp;
    }
    int main( int argc, char *argv[] ) {
    	size_t size = 8096;
    	char *buff = NULL;
    	atexit(foo_atexit);
    	puts("Allocating memory...");
    	if ( !(buff = foo_alloc(NULL,buff,0,size)) )
    		return fail();
    	puts("Clearing memory...");
    	memset(buff,0,size);
    	puts("Filling memory...");
    	strcpy( buff, "Hello World!\n" );
    	puts( buff );
    	puts("Releasing memory...");
    	foo_alloc( NULL, buff, size, 0 );
    	foo__freeall();
    	return EXIT_SUCCESS;
    }

  7. #7
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Decided it was too complex a task to try and put the associative information inside the paged memory so added a variable to foo_page_t and started shifting that information into extra vectors, that fixed the whole alignment issue but leaves me with one bug which I'm just not seeing the cause of right now:
    Code:
    make --no-print-directory alloc
    clang -ggdb -fPIC -fpic -llua -o alloc.elf alloc.c
    gede --args ./alloc.elf
    24.374| INFO  | Using: /dev/pts/2
    24.415| INFO  | Found ctags ('ctags')
    ./alloc.elf
    sizeof(void*) = 8, sizeof(uintptr_t) = 8, sizeof(ptrdiff_t) = 8, sizeof(size_t) = 8
    Allocating memory...
    Clearing memory...
    Filling memory...
    Hello World!
    Releasing memory...
    Error 0x00000016 Invalid argument
    Compilation finished successfully.
    Code:
    #include <limits.h>
    #include <inttypes.h>
    #include <sys/types.h>
    #include <errno.h>
    #include <ctype.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <dirent.h>
    
    #include <string.h>
    #include <sys/mman.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <elf.h>
    
    int fail() {
    	printf("Error 0x%08X %s\n", errno, strerror(errno) );
    	return EXIT_FAILURE;
    }
    
    void foo_atexit() {
    	(void)fail();
    }
    
    typedef unsigned char uchar;
    
    typedef struct foo_vector {
    	long size, used, upto;
    	void *data;
    } foo_vector_t;
    
    int foo_vector_alloc( foo_vector_t *dst, size_t want ) {
    	uchar *tmp;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( want > LONG_MAX ) return ERANGE;
    	if ( dst->data ) {
    		if ( !want ) {
    			free( dst->data );
    			(void)memset(dst,0,sizeof(foo_vector_t));
    			return EXIT_SUCCESS;
    		}
    		tmp = realloc( dst->data, want );
    		check:
    		if ( !tmp ) {
    			if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
    			return errno;
    		}
    		if ( want > dst->size )
    			(void)memset( &tmp[dst->size], 0, want - dst->size );
    		dst->data = tmp;
    		dst->size = want;
    		return EXIT_SUCCESS;
    	}
    	if ( !want ) return (errno = ERANGE);
    	(void)memset( dst, 0, sizeof(foo_vector_t) );
    	tmp = malloc( want );
    	goto check;
    }	
    
    typedef struct foo_addr {
    	long node, page;
    	uintptr_t size, used, spot;
    	void *data;
    } foo_addr_t;
    
    typedef struct foo_page {
    	long node;
    	foo_vector_t blocks;
    	void *base, *data;
    	uintptr_t size, left;
    } foo_page_t;
    
    int page_fd = -1;
    foo_vector_t pages = {0};
    foo_page_t *pagev = NULL;
    #define FOO_ALIGN 16
    int foo_new_page( size_t want ) {
    	uintptr_t p;
    	foo_page_t *page = NULL;
    	if ( pages.used >= pages.upto ) {
    		p = pages.used + 100;
    		if ( (errno =
    			foo_vector_alloc(&pages, sizeof(foo_page_t) * p))
    			!= EXIT_SUCCESS )
    			return errno;
    		pagev = pages.data;
    		if ( page_fd < 0 ) {
    			page_fd = open("/dev/zero", O_RDWR);
    			if ( page_fd < 0 ) {
    				if (errno == EXIT_SUCCESS) errno = EXIT_FAILURE;
    				return errno;
    			}
    		}
    	}
    	p = (pages.used)++;
    	page = &(pagev[p]);
    	page->node = p;
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= ((want % page->size)+1);
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	p = ((uintptr_t)page->base) % FOO_ALIGN;
    	if ( p ) {
    		page->data = page->base + (FOO_ALIGN - p);
    		page->left = page->size - (FOO_ALIGN - p);
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	return EXIT_SUCCESS;
    }
    int foo__del_page( long p ) {
    	if ( p < 0 || p > pages.used ) return ERANGE;
    	foo_vector_alloc( &(pagev[p].blocks), 0 );
    	return munmap( pagev[p].base, pagev[p].size );
    }
    int foo__has_addr(
    	foo_page_t **dst, foo_addr_t **pos, void *ptr ) {
    	long p, a;
    	foo_page_t *page;
    	foo_addr_t *addr, *blockv;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	if ( !ptr ) return EXIT_FAILURE;
    	for ( p = 0; p < pages.used; ++p ) {
    		page = &(pagev[p]);
    		blockv = page->blocks.data;
    		for ( a = 0; a < page->blocks.used; ++a ) {
    			addr = &(blockv[a]);
    			if ( addr->data == ptr ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    		}
    	}
    	return EINVAL;
    }
    int foo__add_blocks( foo_page_t *page ) {
    	long a;
    	foo_addr_t *addr;
    	foo_vector_t *blocks;
    	if ( !page ) return EDESTADDRREQ;
    	blocks = &(page->blocks);
    	if ( blocks->used < 0 ) blocks->used = -1;
    	if ( blocks->upto < blocks->used ) blocks->upto = blocks->used;
    	if ( blocks->used == blocks->upto ) {
    		if ( (errno = foo_vector_alloc( blocks,
    			(blocks->upto + 100) * sizeof(foo_addr_t) ))
    			!= EXIT_SUCCESS ) return errno;
    		blocks->upto += 100;
    		addr = page->blocks.data;
    		for ( a = blocks->used; a < blocks->upto; ++a )
    			addr[a].node = a;
    	}
    	return EXIT_SUCCESS;
    }
    int foo__try_addr(
    	foo_page_t *page, foo_addr_t *addr, size_t want ) {
    	long a, n;
    	foo_addr_t *next = NULL, *blockv;
    	if ( !page || !addr ) return EDESTADDRREQ;
    	if ( !want ) {
    		addr->used = 0;
    		return EXIT_SUCCESS;
    	}
    	a = addr->node;
    	/* Ensure correct alignment */
    	if ( want % FOO_ALIGN ) want += (FOO_ALIGN - (want % FOO_ALIGN));
    	blockv = page->blocks.data;
    	for ( n = a + 1; n < page->blocks.used; ++n ) {
    		next = &(blockv[n]);
    		if ( next->used ) break;
    		addr->size += next->size;
    	}
    	if ( n - a > 1 ) {
    		page->blocks.used -= n - a;
    		if ( n < page->blocks.used ) {
    			memmove( &(blockv[addr->node+1]), next,
    			(n - a) * sizeof(foo_addr_t) );
    			/* Reset node numbers now that we moved the data
    			 * we need to keep n however so substitue a which we
    			 * can reset after*/
    			for ( ++a; a < page->blocks.used; ++a )
    				blockv[a].node = a;
    			/* No need to check alignment,
    			 * already done when appending nodes */
    			a = addr->node;
    		}
    		else {
    			memset( &(blockv[addr->node+1]), 0,
    				(n - a) * sizeof(foo_addr_t) );
    			/* Align next node correctly */
    			if ( addr->size % FOO_ALIGN )
    				addr->size += (FOO_ALIGN - addr->size % FOO_ALIGN);
    			/* Clamp the size if it went over */
    			if ( addr->spot + addr->size > page->size )
    				addr->size = page->size - addr->spot;
    		}
    	}
    	/* Ensure we have enough memory*/
    	if ( addr->size < want ) return ENOMEM;
    	addr->used = want;
    	/* addr->spot is set when creating next node */
    	addr->data = &(((uchar*)(page->data))[addr->spot]);
    	/* Check if we should try creating a new node */
    	if ( n == page->blocks.used && addr->size > want ) {
    		if ( n == page->blocks.upto ) {
    			if ( foo__add_blocks( page ) != EXIT_SUCCESS ) {
    				/* While we got the memory we wanted this the only
    				 * function responsible for adding nodes so fail
    				 * if we can't do that */
    				return ENOMEM;
    			}
    			blockv = page->blocks.data;
    		}
    		next = (foo_addr_t*)(&(blockv[n]));
    		next->spot = addr->spot + want;
    		next->size = addr->size - want;
    		next->page = addr->page;
    		addr->size = want;
    		next->data = &(((uchar*)(page->data))[next->spot]);
    	}
    	return EXIT_SUCCESS;
    }
    int foo__new_addr(
    	foo_page_t **dst, foo_addr_t **pos, size_t want )
    {
    	long p, a;
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *blockv;
    	uintptr_t size;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	for ( p = 0; p < pages.used; ++p ) {
    		size = 0;
    		page = &(pagev[p]);
    		blockv = page->blocks.data;
    		for ( a = 0; a < page->blocks.used; ++a ) {
    			redo:
    			addr = &(blockv[a]);
    			if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    			size += addr->size;
    		}
    		if ( size < page->size ) {
    			if ( (errno = foo__add_blocks( page )) != EXIT_SUCCESS )
    				return errno;
    			blockv = page->blocks.data;
    			goto redo;
    		}
    	}
    	if ( (errno = foo_new_page(want)) != EXIT_SUCCESS )
    		return errno;
    	page = &(pagev[p]);
    	if ( (errno = foo__add_blocks( page )) != EXIT_SUCCESS )
    		return errno;
    	blockv = page->blocks.data;
    	blockv->size = page->size;
    	*dst = page;
    	*pos = blockv;
    	return EXIT_SUCCESS;
    }
    int foo__alloc( void **dst, size_t want ) {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *prev = NULL;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( !want ) {
    		if ((errno = foo__has_addr( &page, &addr, *dst ))
    			!= EXIT_SUCCESS)
    			return errno;
    		*dst = NULL;
    		addr->used = 0;
    		return EXIT_SUCCESS;
    	}
    	if ( *dst ) {
    		if ((errno = foo__has_addr(&page,&prev,*dst))
    			!= EXIT_SUCCESS)
    			return errno;
    		if ( foo__try_addr( page, prev, want ) == EXIT_SUCCESS ) {
    			return EXIT_SUCCESS;
    		}
    		if ( (errno = foo__new_addr( &page, &addr, want ))
    			!= EXIT_SUCCESS )
    			return errno;
    		*dst = memcpy( addr->data, prev->data, prev->size );
    		prev->used = 0;
    		return EXIT_SUCCESS;
    	}
    	if ( (errno = foo__new_addr( &page, &addr, want ))
    		!= EXIT_SUCCESS )
    		return errno;
    	if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    		return errno;
    	*dst = addr->data;
    	return EXIT_SUCCESS;
    }
    void foo__freeall() {
    	long p;
    	for ( p = 0; p < pages.used; ++p ) foo__del_page( p );
    	foo_vector_alloc( &pages, 0 );
    	pagev = NULL;
    	if ( page_fd >= 0 ) close(page_fd);
    }
    void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
    	uchar *tmp = ptr;
    	(void)ud;
    	if ( (errno = foo__alloc( (void**)(&tmp), want ))
    		!= EXIT_SUCCESS )
    		return NULL;
    	if ( !want ) return NULL;
    	if ( !ptr || !size ) memset( tmp, 0, want );
    	if ( size < want ) memset( &tmp[size], 0, want - size );
    	return tmp;
    }
    int main( int argc, char *argv[] ) {
    	size_t size = 8096;
    	char *buff = NULL;
    	printf("sizeof(void*) = %zu, "
    		"sizeof(uintptr_t) = %zu, "
    		"sizeof(ptrdiff_t) = %zu, "
    		"sizeof(size_t) = %zu\n",
    		sizeof(void*), sizeof(uintptr_t), sizeof(ptrdiff_t), sizeof(size_t) );
    	atexit(foo_atexit);
    	puts("Allocating memory...");
    	if ( !(buff = foo_alloc(NULL,buff,0,size)) )
    		return fail();
    	puts("Clearing memory...");
    	memset(buff,0,size);
    	puts("Filling memory...");
    	strcpy( buff, "Hello World!\n" );
    	puts( buff );
    	puts("Releasing memory...");
    	foo_alloc( NULL, buff, size, 0 );
    	foo__freeall();
    	return EXIT_SUCCESS;
    }

  8. #8
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Just noticed a typo, where page->size is being increased before calling mmap() I used % instead of /
    I think the bug I was experiencing before was just a result of not clearing errno at an appropriate time, haven't find when but I must've valed it in my attempt to catch it from the release functions, bug is still there but not end of the world, I'll just wait till someone who's interested enough to try posts about it. Oh btw for a license just consider the code on this thread under MIT LIcense

  9. #9
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    I've managed to fix the bug I think, forgot to set the address of the data in a couple of places, so I got past my initial use of them but now lua is complaining of something, gonna go see if there is a debug-able version mentioned on the official site and try that but in case there isn't or someone feels like looking through the code themselves here's the updated copy-paste file with lua added in (already confirmed it compiles & runs fine without lua):
    Code:
    #include <limits.h>
    #include <inttypes.h>
    #include <sys/types.h>
    #include <errno.h>
    #include <ctype.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <dirent.h>
    
    #include <string.h>
    #include <sys/mman.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <elf.h>
    
    #include <lua.h>
    #include <lauxlib.h>
    #include <lualib.h>
    
    int fail() {
    	if ( errno != EXIT_SUCCESS )
    		printf("Error 0x%08X %s\n", errno, strerror(errno) );
    	return EXIT_FAILURE;
    }
    
    void foo_atexit() {
    	(void)fail();
    }
    
    typedef unsigned char uchar;
    
    typedef struct foo_vector {
    	long size, used, upto;
    	void *data;
    } foo_vector_t;
    
    int foo_vector_alloc( foo_vector_t *dst, size_t want ) {
    	uchar *tmp;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( want > LONG_MAX ) return ERANGE;
    	if ( dst->data ) {
    		if ( !want ) {
    			free( dst->data );
    			(void)memset(dst,0,sizeof(foo_vector_t));
    			return EXIT_SUCCESS;
    		}
    		tmp = realloc( dst->data, want );
    		check:
    		if ( !tmp ) {
    			if ( errno == EXIT_SUCCESS )
    				errno = ENOMEM;
    			return errno;
    		}
    		if ( want > dst->size )
    			(void)memset( &tmp[dst->size], 0, want - dst->size );
    		dst->data = tmp;
    		dst->size = want;
    		return EXIT_SUCCESS;
    	}
    	if ( !want ) return (errno = ERANGE);
    	(void)memset( dst, 0, sizeof(foo_vector_t) );
    	tmp = malloc( want );
    	goto check;
    }	
    
    typedef struct foo_addr {
    	long node, page;
    	uintptr_t size, used, spot;
    	void *data;
    } foo_addr_t;
    
    typedef struct foo_page {
    	long node;
    	foo_vector_t blocks;
    	void *base, *data;
    	uintptr_t size, left;
    } foo_page_t;
    
    int page_fd = -1;
    foo_vector_t pages = {0};
    foo_page_t *pagev = NULL;
    #define FOO_ALIGN 16
    int foo__new_page( size_t want ) {
    	uintptr_t p;
    	foo_page_t *page = NULL;
    	if ( pages.used >= pages.upto ) {
    		p = pages.used + 100;
    		if ( (errno =
    			foo_vector_alloc(&pages, sizeof(foo_page_t) * p))
    			!= EXIT_SUCCESS )
    			return errno;
    		pagev = pages.data;
    		pages.upto = p;
    		if ( page_fd < 0 ) {
    			page_fd = open("/dev/zero", O_RDWR);
    			if ( page_fd < 0 ) {
    				if (errno == EXIT_SUCCESS) errno = EXIT_FAILURE;
    				return errno;
    			}
    		}
    	}
    	p = (pages.used)++;
    	page = &(pagev[p]);
    	page->node = p;
    	page->size = sysconf(_SC_PAGESIZE);
    	if ( want > page->size ) page->size *= ((want / page->size)+1);
    	page->base = mmap( NULL, page->size,
    		PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
    	p = ((uintptr_t)page->base) % FOO_ALIGN;
    	if ( p ) {
    		page->data = (void*)(((uintptr_t)(page->base)) + (FOO_ALIGN - p));
    		page->left = page->size - (FOO_ALIGN - p);
    	}
    	else {
    		page->data = page->base;
    		page->left = page->size;
    	}
    	return EXIT_SUCCESS;
    }
    int foo__del_page( long p ) {
    	if ( p < 0 || p > pages.used ) return ERANGE;
    	foo_vector_alloc( &(pagev[p].blocks), 0 );
    	return munmap( pagev[p].base, pagev[p].size );
    }
    int foo__has_addr(
    	foo_page_t **dst, foo_addr_t **pos, void *ptr ) {
    	long p, a;
    	foo_page_t *page;
    	foo_addr_t *addr, *blockv;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	if ( !ptr ) return EXIT_FAILURE;
    	for ( p = 0; p < pages.used; ++p ) {
    		page = &(pagev[p]);
    		blockv = page->blocks.data;
    		for ( a = 0; a < page->blocks.used; ++a ) {
    			addr = &(blockv[a]);
    			if ( addr->data == ptr ) {
    				*dst = page;
    				*pos = addr;
    				return EXIT_SUCCESS;
    			}
    		}
    	}
    	return EINVAL;
    }
    int foo__add_blocks( foo_page_t *page ) {
    	long a;
    	foo_addr_t *addr;
    	foo_vector_t *blocks;
    	if ( !page ) return EDESTADDRREQ;
    	blocks = &(page->blocks);
    	if ( blocks->used < 0 ) blocks->used = -1;
    	if ( blocks->upto < blocks->used ) blocks->upto = blocks->used;
    	if ( blocks->used == blocks->upto ) {
    		if ( (errno = foo_vector_alloc( blocks,
    			(blocks->upto + 100) * sizeof(foo_addr_t) ))
    			!= EXIT_SUCCESS ) return errno;
    		blocks->upto += 100;
    		addr = page->blocks.data;
    		for ( a = blocks->used; a < blocks->upto; ++a )
    			addr[a].node = a;
    	}
    	return EXIT_SUCCESS;
    }
    int foo__try_addr(
    	foo_page_t *page, foo_addr_t *addr, size_t want ) {
    	long a, n;
    	foo_addr_t *next = NULL, *blockv;
    	if ( !page || !addr )
    		return EDESTADDRREQ;
    	if ( want <= addr->used ) {
    		addr->used = want;
    		return EXIT_SUCCESS;
    	}
    	a = addr->node;
    	/* Ensure correct alignment */
    	if ( want % FOO_ALIGN ) want += (FOO_ALIGN - (want % FOO_ALIGN));
    	blockv = page->blocks.data;
    	for ( n = a + 1; n < page->blocks.used; ++n ) {
    		next = &(blockv[n]);
    		if ( next->used ) break;
    		addr->size += next->size;
    	}
    	if ( n - a > 1 ) {
    		page->blocks.used -= n - a;
    		if ( n < page->blocks.used ) {
    			memmove( &(blockv[addr->node+1]), next,
    			(n - a) * sizeof(foo_addr_t) );
    			/* Reset node numbers now that we moved the data
    			 * we need to keep n however so substitue a which we
    			 * can reset after*/
    			for ( ++a; a < page->blocks.used; ++a )
    				blockv[a].node = a;
    			/* No need to check alignment,
    			 * already done when appending nodes */
    			a = addr->node;
    		}
    		else {
    			memset( &(blockv[addr->node+1]), 0,
    				(n - a) * sizeof(foo_addr_t) );
    			/* Align next node correctly */
    			if ( addr->size % FOO_ALIGN )
    				addr->size += (FOO_ALIGN - addr->size % FOO_ALIGN);
    			/* Clamp the size if it went over */
    			if ( addr->spot + addr->size > page->size )
    				addr->size = page->size - addr->spot;
    		}
    	}
    	/* Ensure we have enough memory */
    	if ( addr->size < want )
    		return ENOMEM;
    	addr->used = want;
    	/* addr->spot is set when creating next node */
    	addr->data = &(((uchar*)(page->data))[addr->spot]);
    	/* Check if we should try creating a new node */
    	if ( n == page->blocks.used && addr->size > want ) {
    		if ( n == page->blocks.upto ) {
    			if ( foo__add_blocks( page ) != EXIT_SUCCESS ) {
    				/* While we got the memory we wanted this is the only
    				 * function responsible for adding nodes so fail
    				 * if we can't do that */
    				return ENOMEM;
    			}
    			blockv = page->blocks.data;
    		}
    		page->blocks.used++;
    		next = (foo_addr_t*)(&(blockv[n]));
    		next->spot = addr->spot + want;
    		next->data = &(((uchar*)(page->data))[next->spot]);
    		next->size = addr->size - want;
    		next->page = addr->page;
    		addr->size = want;
    	}
    	return EXIT_SUCCESS;
    }
    int foo__new_addr(
    	foo_page_t **dst, foo_addr_t **pos, size_t want )
    {
    	long p, a;
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *blockv;
    	uintptr_t size;
    	if ( !dst || !pos ) return EDESTADDRREQ;
    	*dst = NULL;
    	*pos = NULL;
    	for ( p = 0; p < pages.used; ++p ) {
    		size = 0;
    		page = &(pagev[p]);
    		blockv = page->blocks.data;
    		for ( a = 0; a < page->blocks.used; ++a ) {
    			redo:
    			addr = &(blockv[a]);
    			if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS )
    				goto success;
    			size += addr->size;
    		}
    		if ( size < page->size ) {
    			if ( (errno = foo__add_blocks( page )) != EXIT_SUCCESS )
    				return errno;
    			blockv = page->blocks.data;
    			goto redo;
    		}
    	}
    	if ( (errno = foo__new_page(want)) != EXIT_SUCCESS )
    		return errno;
    	page = &(pagev[p]);
    	if ( (errno = foo__add_blocks( page )) != EXIT_SUCCESS )
    		return errno;
    	page->blocks.used = 1;
    	addr = page->blocks.data;
    	addr->size = page->size;
    	success:
    	*dst = page;
    	*pos = addr;
    	addr->used = want;
    	addr->data = &(((uchar*)(page->data))[addr->spot]);
    	return (errno = EXIT_SUCCESS);
    }
    int foo__alloc( void **dst, size_t want ) {
    	foo_page_t *page = NULL;
    	foo_addr_t *addr = NULL, *prev = NULL;
    	if ( !dst ) return EDESTADDRREQ;
    	if ( !want ) {
    		if ((errno = foo__has_addr( &page, &addr, *dst ))
    			!= EXIT_SUCCESS)
    			return errno;
    		*dst = NULL;
    		addr->used = 0;
    		return EXIT_SUCCESS;
    	}
    	if ( *dst ) {
    		if ((errno = foo__has_addr(&page,&prev,*dst))
    			!= EXIT_SUCCESS)
    			return errno;
    		if ( foo__try_addr( page, prev, want ) == EXIT_SUCCESS )
    			return EXIT_SUCCESS;
    		if ( (errno = foo__new_addr( &page, &addr, want ))
    			!= EXIT_SUCCESS )
    			return errno;
    		if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    			return errno;
    		(void)memcpy( (*dst = addr->data), prev->data, prev->size );
    		prev->used = 0;
    		return EXIT_SUCCESS;
    	}
    	if ( (errno = foo__new_addr( &page, &addr, want ))
    		!= EXIT_SUCCESS )
    		return errno;
    	if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
    		return errno;
    	*dst = addr->data;
    	return EXIT_SUCCESS;
    }
    void foo__freeall() {
    	long p;
    	for ( p = 0; p < pages.used; ++p ) {
    		if ( (errno = foo__del_page( p )) != EXIT_SUCCESS )
    			exit(errno);
    	}
    	if ( (errno = foo_vector_alloc( &pages, 0 )) != EXIT_SUCCESS )
    		exit(errno);
    	pagev = NULL;
    	if ( page_fd >= 0 ) close(page_fd);
    }
    void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
    	uchar *tmp = ptr;
    	(void)ud;
    	if ( (errno = foo__alloc( (void**)(&tmp), want ))
    		!= EXIT_SUCCESS )
    		return NULL;
    	if ( !want ) return NULL;
    	if ( !ptr || !size ) memset( tmp, 0, want );
    	if ( size < want ) memset( &tmp[size], 0, want - size );
    	return tmp;
    }
    int main( int argc, char *argv[] ) {
    	size_t size = 8096;
    	char *buff = NULL;
    	lua_State *L = NULL;
    	atexit(foo_atexit);
    	printf("sizeof(void*) = %zu, "
    		"sizeof(uintptr_t) = %zu, "
    		"sizeof(ptrdiff_t) = %zu, "
    		"sizeof(size_t) = %zu\n",
    		sizeof(void*), sizeof(uintptr_t), sizeof(ptrdiff_t), sizeof(size_t) );
    	puts("Allocating memory...\n");
    	if ( !(buff = foo_alloc(NULL,buff,0,size)) )
    		return fail();
    	puts("Clearing memory...\n");
    	memset(buff,0,size);
    	puts("Filling memory...\n");
    	strcpy( buff, "Hello World!\n" );
    	puts( buff );
    	puts("Releasing memory...\n");
    	foo_alloc( NULL, buff, size, 0 );
    	puts("Initiating Lua...\n");
    	if ( (L = lua_newstate( foo_alloc, NULL )) ) {
    		puts("Closing Lua...\n");
    		lua_close(L);
    	}
    	puts("Releasing pages...\n");
    	foo__freeall();
    	return EXIT_SUCCESS;
    }
    Edit: Nope couldn't find it, google keeps directing me to the internal debug library meant for lua debugging not for c debugging, anyone know of the right lib?
    Last edited by awsdert; 01-05-2020 at 05:09 AM.

  10. #10
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    After downloading lua's source code and compiling with the -ggdb and -O0 flags I found that lua was crashing because it's global state pointer was somehow overridden, but trying to find the cause of that was like looking for a needle in a haystack so I ended up having to split off adding and removing address objects to new functions and that stopped lua segfaulting at the early stages, somehow however lua still segfaults later due to what looks like memory corruption, I need a break and so am gonna get something to eat so I just attached the file I'm testing with to see if anyone feels like checking it out while I'm gone, I also got gospel later so might not be back before the end of that
    Attached Files Attached Files

  11. #11
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Well I found A reason why some of the segfaults happen, apparently not allowed to use ALL the assigned memory, have to leave (sizeof(void*)*CHAR_BIT) unused at the end of the assigned memory (page->size -(sizeof(void*)*CHAR_BIT)) from a mmap() call, attempting to access it causes a segfault. Found that out while restarting with a new idea for keeping the address list in the page,
    I'm now doing it as data = (ptr + offset) and addr = (((ptr + page size) - (sizeof(void*)*CHAR_BIT)) - sizeof(list struct)) - (i * sizeof(addr))

  12. #12
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Well spent a few hours implementing my new method and tried running it, at 1st I had segfaults due to forgetting to remove pages from a list when un-mapping a page, once I fixed that I had a different segfault caused by somehow getting NULL in locations it seems impossible to reach as far as I can see, I attached the file and the places getting NULL are where the basic page information should be (despite me explicitly setting that information straight after confirming successful retrieval), I'm drawing a blank right now so just gonna mention the line it segfaults on and take a break, hopefully someone else will figure it out by the time I get back, line 266, doesn't even reach lua but gets past the initial test of page allocation & de-allocation.
    Attached Files Attached Files

  13. #13
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Took a while to find this instance of the problem but I found out that somehow I'm not incrementing the start address to seize from in my own allocation functions (only caught after stepping through lua's initial call system and watching the values, I hate how slow that was), anyways now I know roughly where to look I can try to fix it, but just in case someone else gets there faster than me I've attached the file again.
    Attached Files Attached Files

  14. #14
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Well the source issue was quickly resolved by moving the subtraction from page->last->upto to above the pointer override and replacing the pointer override with spot = page->init = (std_spot*)(&(((uchar*)(page->last->data.data))[page->last->upto]));
    Not greatly readable but at least one can see reasonably easily what is going on there, had to fix a bunch of other errors that I spotted along the way, still segfaulting inside lua but now I know for sure any remaining errors are inside this function:
    Code:
    int alloc_foo_data( std_data *_data, long want ) {
    	long p, a, need;
    	foo_page *page, *pages;
    	std_spot *spot, *init, temp = {0};
    	if ( !_data ) return EDESTADDRREQ;
    	pages = page_list.data.data;
    	if ( _data->data ) {
    		for ( p = 0; p < page_list.used; ++p ) {
    			page = &(pages[p]);
    			for ( a = 1,
    				spot = page->init;
    				spot != page->last;
    				++a, spot = &(spot[1])
    			)
    			{
    				if ( _data->data == spot->data.data ) break;
    			}
    			if ( spot != page->last ) break;
    		}
    		if ( p == page_list.used )
    			return EINVAL;
    		if ( spot->upto - spot->from >= want ) {
    			spot->data.size = want;
    			if ( want <= 0 ) {
    				_data->size = 0;
    				_data->data = NULL;
    				if ( &(page->init[a]) < page->last )
    					(void)memmove(
    						&(page->init[a]), page->init,
    						a * sizeof(std_spot) );
    				page->init = &(page->init[a]);
    				page->last->upto += sizeof(std_spot);
    				return EXIT_SUCCESS;
    			}
    			_data->size = want;
    			_data->data = spot->data.data;
    			return EXIT_SUCCESS;
    		}
    	}
    	_data->data = NULL;
    	_data->size = 0;
    	need = want + sizeof(std_spot);
    	for ( p = 0; p < page_list.used; ++p ) {
    		page = &(pages[p]);
    		if ( page->last->upto < need ) continue;
    		if ( page->init == page->last ) {
    			whole_page:
    			page->last->upto -= sizeof(std_spot);
    			spot = page->init = (std_spot*)
    				(&(((uchar*)(page->last->data.data))[page->last->upto]));
    			spot->data.data = page->last->data.data;
    			spot->upto = page->last->upto;
    			spot->data.size = want;
    			spot->from = 0;
    			*_data = spot->data;
    			return EXIT_SUCCESS;
    		}
    		for ( a = 1,
    			spot = page->init;
    			spot != page->last;
    			++a, spot = &(spot[1])
    		)
    		{
    			if  ( (spot->upto - spot->from) - spot->data.size < want )
    				continue;
    			if ( spot->upto == page->last->upto ) {
    				if  ( (spot->upto - spot->from)
    					- spot->data.size < need )
    					break;
    				spot->upto -= sizeof(std_spot);
    			}
    			temp.upto = spot->upto;
    			temp.from = spot->data.size;
    			spot->upto = spot->from + spot->data.size;
    			temp.data.size = want;
    			temp.data.data =
    				&(((uchar*)(page->last->data.data))[temp.from]);
    			page->last->upto -= sizeof(std_spot);
    			init = (std_spot*)
    				(&(((uchar*)(page->last->data.data))[page->last->upto]));
    			(void)memmove( init, page->init, a * sizeof(std_spot) );
    			page->init = init;
    			*spot = temp;
    			*_data = spot->data;
    			return EXIT_SUCCESS;
    		}
    	}
    	if ( (a = alloc_foo_page( &p, want )) != EXIT_SUCCESS )
    		return a;
    	pages = page_list.data.data;
    	page = &(pages[p]);
    	goto whole_page;
    }

  15. #15
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    839
    Finally, fixed that segfault, had to remove line 74 from previous post and change line 73 to this:
    Code:
    temp.from = spot->upto = spot->from + spot->data.size;
    Now however line 28 is giving me a segfault when attempting to close the lua state

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help With Aligning
    By M_A_T_T in forum C Programming
    Replies: 2
    Last Post: 02-13-2013, 05:44 AM
  2. Right aligning.
    By theCanuck in forum C++ Programming
    Replies: 2
    Last Post: 02-12-2011, 12:50 PM
  3. Aligning Columns
    By mike_g in forum C Programming
    Replies: 3
    Last Post: 06-27-2007, 08:27 AM
  4. Aligning text
    By Bad_Scooter in forum C++ Programming
    Replies: 5
    Last Post: 06-04-2003, 12:06 PM

Tags for this Thread