a.md

UPDATE: See "Update" below

Problem

What can cause unaligned pointers to end up on my stack? Or: what, on my stack, can look like unaligned pointers?

Context is that I'm trying to write a conservative GC. I want to scan the stack for things that look like pointers (and then mark them, but I'm not at that point yet). I copied & hacked together some code from other GCs I found, which essentially does the following:

1. At program start: save the current %rbp away as the "stack bottom" (highest address)
2. When scanning stack: save now-current %rbp away as "stack top" (lowest address)
3. Walk from "stack top" to "stack bottom" in word-size increments, look into each stack slot, check if it's pointer

The problem: I do find pointers and I even find the pointers I previously put on the stack, but there are other looks-like-pointer things on there, except they are unaligned (lowest 3 bits aren't 0). My goal was to tag my pointers (change lowest 3 bits) and then use that tag to recognize which pointers are mine. Finding other stuff on the stack that also looks like it's tagged is obviously a problem.

Reproducible example

Run gc_experiment2.c by doing:

gcc -o gc_experiment2 ./gc_experiment2.c && ./gc_experiment2 

Output

The program will print every stack slot (stack_slot=) and what's in it (content=).

Some of the content is the local_* vars put on there earlier. But there are other pointer-lookalike things on there that are not aligned.

I marked them in the output here:

&local_a_3: 0x7ffc9c497460 (33)
&local_a_2: 0x559ecd018350
&local_a_1: 0x559ecd0182a0
----------
&local_b_3: 0x7ffc9c497430 (66)
&local_b_2: 0x559ecd0188b0
&local_b_1: 0x559ecd018780
----------
&local_c_3: 0x7ffc9c497400 (99)
&local_c_2: 0x559ecd018b00
&local_c_1: 0x559ecd0188d0
----------
scan_stack. stack_top: 0x7ffc9c4973f0, stack_bottom: 0x7ffc9c497480 (18 words)
stack_slot=0x7ffc9c4973f0 content=0x7ffc9c497420        <---------- old base pointer
stack_slot=0x7ffc9c4973f8 content=0x559ecb017425        <---------- UNALIGNED
stack_slot=0x7ffc9c497400 content=0x63                  <---------- local_c_3
stack_slot=0x7ffc9c497408 content=0x559ecd0188d0        <---------- local_c_1
stack_slot=0x7ffc9c497410 content=0x559ecd018b00        <---------- local_c_2
stack_slot=0x7ffc9c497418 content=0xcc165d590c527100
stack_slot=0x7ffc9c497420 content=0x7ffc9c497450        <---------- old base pointer
stack_slot=0x7ffc9c497428 content=0x559ecb0174f3        <---------- UNALIGNED
stack_slot=0x7ffc9c497430 content=0x42                  <---------- local_b_3
stack_slot=0x7ffc9c497438 content=0x559ecd018780        <---------- local_b_1
stack_slot=0x7ffc9c497440 content=0x559ecd0188b0        <---------- local_b_2
stack_slot=0x7ffc9c497448 content=0xcc165d590c527100
stack_slot=0x7ffc9c497450 content=0x7ffc9c497480        <---------- old base pointer
stack_slot=0x7ffc9c497458 content=0x559ecb0175c1        <---------- UNALIGNED
stack_slot=0x7ffc9c497460 content=0x21                  <---------- local_a_3
stack_slot=0x7ffc9c497468 content=0x559ecd0182a0        <---------- local_a_1
stack_slot=0x7ffc9c497470 content=0x559ecd018350        <---------- local_a_2
stack_slot=0x7ffc9c497478 content=0xcc165d590c527100

Update

Okay, I figured it out.

1. Unaligned pointers are the return addresses
2. The other, really big values on the stack are GCC's stack protectors

STACK TOP (lowest address)
0x7ffc88292850 content=0x7ffc88292880     aligned=1   <--- old sp --------|
0x7ffc88292858 content=0x5555a3f4145f     aligned=0   <--- return addr    |
0x7ffc88292860 content=0x63               aligned=0   <--- local_c_3      |
0x7ffc88292868 content=0x5555a5e998d0     aligned=1   <--- local_c_1      |
0x7ffc88292870 content=0x5555a5e99b00     aligned=1   <--- local_c_2      |
0x7ffc88292878 content=0xbc9fa69ab4faa300 aligned=1   <--- stack protector|
0x7ffc88292880 content=0x7ffc882928b0     aligned=1   <--- old sp ------<-|
0x7ffc88292888 content=0x5555a3f4152d     aligned=0   <--- return addr    |
0x7ffc88292890 content=0x42               aligned=1   <--- local_b_3      |
0x7ffc88292898 content=0x5555a5e99780     aligned=1   <--- local_b_1      |
0x7ffc882928a0 content=0x5555a5e998b0     aligned=1   <--- local_b_2      |
0x7ffc882928a8 content=0xbc9fa69ab4faa300 aligned=1   <--- stack protector|
0x7ffc882928b0 content=0x7ffc882928e0     aligned=1   <--- old sp ------<-|
0x7ffc882928b8 content=0x5555a3f415fb     aligned=0   <--- return addr
0x7ffc882928c0 content=0x21               aligned=0   <--- local_a_3
0x7ffc882928c8 content=0x5555a5e992a0     aligned=1   <--- local_a_1
0x7ffc882928d0 content=0x5555a5e99350     aligned=1   <--- local_a_2
0x7ffc882928d8 content=0xbc9fa69ab4faa300 aligned=1   <--- stack protector
STACK BOTTOM (highest address)

gc_experiment2.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tucan_string {
  int length;
  char *chars;
} tucan_string;

static tucan_string *allocate_string(char *chars, int length) {
  tucan_string *string = (tucan_string *)malloc(sizeof(tucan_string));
  string->length = length;
  string->chars = chars;

  return string;
}

tucan_string *make_string(const char *chars, int length) {
  char *heap_chars = (char *)malloc(sizeof(char) * (length + 1));
  memcpy(heap_chars, chars, length);
  heap_chars[length] = '\0';

  return allocate_string(heap_chars, length);
}

static void *stack_bottom;

static void scan_stack(void *from_, void *to_) {
  void **from = from_;
  void **to = to_;

  printf("scan_stack. stack_top: %p, stack_bottom: %p (%zu words)\n", from, to,
         (size_t)(to - from));

  for (; from < to; from++) {
    void *ptr = *from;
    if (!ptr) {
      continue;
    }

    printf("stack_slot=%p content=%-18p\n", from, ptr);
  }
  printf("------------\n");
}

static void __attribute__((noinline)) gc_collect() {
  void *stack_top;
  asm volatile("movq  %%rbp, %0" : "=r"(stack_top));
  scan_stack(stack_top, stack_bottom);
}

static inline void gc_init() {
  asm volatile("movq  %%rbp, %0" : "=r"(stack_bottom));
}

void function_c() {
  void *local_c_1 = malloc(512);
  void *local_c_2 = make_string("local_c_2", 9);
  int64_t local_c_3 = 99;

  printf("&local_c_3: %p (%ld)\n", &local_c_3, local_c_3);
  printf("&local_c_2: %p\n", local_c_2);
  printf("&local_c_1: %p\n", local_c_1);
  printf("----------\n");

  gc_collect();
}

void function_b() {
  void *local_b_1 = malloc(256);
  void *local_b_2 = make_string("local_b_2", 9);
  int64_t local_b_3 = 66;

  printf("&local_b_3: %p (%ld)\n", &local_b_3, local_b_3);
  printf("&local_b_2: %p\n", local_b_2);
  printf("&local_b_1: %p\n", local_b_1);
  printf("----------\n");

  function_c();
}

void function_a() {
  void *local_a_1 = malloc(128);
  void *local_a_2 = make_string("local_a_2", 9);
  int64_t local_a_3 = 33;

  printf("&local_a_3: %p (%ld)\n", &local_a_3, local_a_3);
  printf("&local_a_2: %p\n", local_a_2);
  printf("&local_a_1: %p\n", local_a_1);
  printf("----------\n");

  function_b();
}

int main(int argc, char *argv[]) {
  gc_init();
  function_a();
  printf("\n");
}