Strdup 非依赖实现(转储 malloc 依赖)

Question

我有一个自定义的实现_strdup。它不应该有任何依赖项，这意味着我不能使用 CRT 或任何内置内容。下面的代码工作正常。唯一的问题是这取决于malloc.因此，我不能将其与/NODEFAULTLIB一起使用，除非我实现自己的malloc。

对非依赖实现有什么想法吗？或者至少是一个malloc/free实现。我什至会接受shellcode实现。

size_t __strlen(const char* str)
{
const char* s;
for (s = str; *s; ++s)
;
return (s - str);
}
void* __memcpy(void* to, const void* from, size_t count)
{
register char* f = (char*)from;
register char* t = (char*)to;
register size_t i = count;
while (i-- > 0)
*t++ = *f++;
return to;
}
char* __strdup(const char* str)
{
size_t len;
char* copy;
len = __strlen(str) + 1;
if (!(copy = (char*)malloc(len)))
return nullptr;
__memcpy(copy, str, len);
return copy;
}

我发现了一个损坏的malloc实现：

#define MEMORY_CAPACITY 20000
void* mov_sbrk(int increment)
{
static char global_mem[MEMORY_CAPACITY] = { 0 };
static char* p_break = global_mem;
char* const limit = global_mem + MEMORY_CAPACITY;
char* const original = p_break;
if (increment < global_mem - p_break || increment >= limit - p_break)
{
errno = ENOMEM;
return (void*)-1;
}
p_break += increment;
return original;
}
//=======================================================================
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
typedef struct list_t list_t;
struct list_t 
{
unsigned    in_use : 1;     /* if the block is used or not */
size_t      order;      /* current order of block (2^order) */
list_t* succ;       /* right child block in tree */
list_t* pred;       /* left child block in tree */
};
#define K_MAX 22
#define K_MAX_SIZE (1 << K_MAX)
#define ORDER_0 4
// Size of the node metadata
#define META_SIZE (ALIGN(sizeof(list_t)))
static list_t* find_block(size_t);
static size_t get_order(size_t);
static list_t* split(list_t*, size_t);
/* Array of pointers to first block of order k at free_list[k] */
static list_t* freelist[K_MAX + 1];
static void* start = NULL;
static void print_freelist()
{
for (int i = ORDER_0; i <= K_MAX; i++) 
{
int f = 0;
int j = 0;
list_t* current = freelist[i];
while (current)
{
if (!current->in_use) 
{
f++;
}
j++;
current = current->succ;
}
}
}
void* malloc(size_t requested_size)
{
print_freelist();
if (requested_size <= 0)
{
return NULL;
}
if (!start)
{
// First allocation ever, grab memory and root the tree
start = mov_sbrk(K_MAX_SIZE);
list_t* top = reinterpret_cast<list_t*>(start);
top->order = K_MAX;
top->in_use = 0;
top->succ = NULL;
top->pred = NULL;
freelist[K_MAX] = top;
}
/* E.g. if requested size is 56 bytes, k = 6 (2^6=64)*/
size_t k = get_order(ALIGN(requested_size + META_SIZE));
list_t* r = find_block(k);
if (r) {
r->in_use = 1;
print_freelist();
return (r + 1);
}
else {
return NULL;
}
}
/* Find the smallest power of 2 larger than k */
static size_t get_order(size_t v)
{
int k = ORDER_0;
while ((1 << k) < v) {
k++;
}
return k;
}
// finds a suitable block of order k. if not found return null
static list_t* find_block(size_t k)
{
if (k > K_MAX)
return NULL;
list_t* current = freelist[k];
while (current) {
if (!current->in_use)
return current;
current = current->succ;
}
list_t* big_block = find_block(k + 1);
if (big_block) {
current = split(big_block, k);
}
return current;
}
static void remove_from_freelist(list_t* item)
{
size_t k = item->order;
if (freelist[k] == item)
freelist[k] = item->succ;
if (item->pred)
item->pred->succ = item->succ;
if (item->succ)
item->succ->pred = item->pred;
item->pred = NULL;
item->succ = NULL;
}
static void add_to_freelist(list_t* item)
{
size_t k = item->order;
if (!freelist[k])
{
freelist[k] = item;
item->succ = NULL;
item->pred = NULL;
return;
}
item->pred = NULL;
item->succ = freelist[k];
freelist[k]->pred = item;
freelist[k] = item;
}
static list_t* split(list_t* src, size_t new_order)
{
while (src->order > new_order)
{
/* src becomes left buddy */
remove_from_freelist(src);
// set new order
src->order = src->order - 1;
// calculate half size of old block, aka size of new order.
size_t size = 1 << src->order;
list_t* right = reinterpret_cast<list_t*>(src + size);
right->order = src->order;
right->in_use = 0;
add_to_freelist(right);
add_to_freelist(src);
}
return src;
}
static void merge(list_t* block)
{
if (block->in_use || block->order == K_MAX)
return;
list_t* buddy = (list_t*)((uint64_t)start + (block - start) ^ (1 << block->order));
if (buddy->in_use || buddy->order != block->order)
return;
list_t* left = block;
list_t* right = buddy;
if (block > buddy) {
left = buddy;
right = block;
}
remove_from_freelist(right);
remove_from_freelist(left);
left->order++;
add_to_freelist(left);
merge(left);
}

void free(void* ptr)
{
print_freelist();
if (!ptr)
return;
list_t* block = (((list_t*)ptr) - 1);
block->in_use = 0;
merge(block);
print_freelist();
}
void* calloc(size_t nbr_elements, size_t element_size) 
{
size_t size = nbr_elements * element_size;
void* ptr = malloc(size);
if (ptr == NULL)
return NULL;
memset(ptr, 0, size);
return ptr;
}
void* realloc(void* ptr, size_t size)
{
if (!ptr) {
return malloc(size);
}
list_t* block = (((list_t*)ptr) - 1);
if ((1 << block->order) - META_SIZE >= size) {
return ptr;
}
void* new_ptr = malloc(size);
if (!new_ptr) {
return NULL;
}
memcpy(new_ptr, ptr, (1 << block->order) - META_SIZE);
free(ptr);
return new_ptr;
}

Answer 1

既然你提到了/nodefaultlib选项，似乎你在Windows上。然后，您可以直接使用 Windows API 函数HeapAlloc()而不是使用malloc()然后HeapFree()稍后免费复制字符串。您可能希望将它们包装到您自己的__malloc()和__free()中，如下所示：

void* __malloc(size_t size)
{
return HeapAlloc(GetProcessHeap(), 0, size); 
}
void __free(void* p)
{
if (p) HeapFree(GetProcessHeap(), 0, p); 
}