<commit_before>//
// Allocate objects smaller than a page.
//

#include "types.h"
#include "mmu.h"
#include "kernel.hh"
#include "spinlock.h"
#include "kalloc.hh"
#include "mtrace.h"
#include "cpu.hh"

// allocate in power-of-two sizes up to 2^KMMAX
// must be < 12
#define KMMAX 11

struct header {
  struct header *next;
};

struct freelist {
  struct header *buckets[KMMAX+1];
  char name[MAXNAME];
  struct spinlock lock;
};

struct freelist freelists[NCPU];

void
kminit(void)
{
  for (int c = 0; c < NCPU; c++) {
    freelists[c].name[0] = (char) c + '0';
    safestrcpy(freelists[c].name+1, "freelist", MAXNAME-1);
    initlock(&freelists[c].lock, freelists[c].name, LOCKSTAT_KMALLOC);
  }
}

// get more space for freelists[c].buckets[b]
void
morecore(int c, int b)
{
  char *p = kalloc();
  if(p == 0)
    return;

  int sz = 1 << b;
  for(char *q = p;
      q + sz + sizeof(struct header) <= p + PGSIZE;
      q += sz + sizeof(struct header)){
    struct header *h = (struct header *) q;
    h->next = freelists[c].buckets[b];
    freelists[c].buckets[b] = h;
  }
}

void *
kmalloc(u64 nbytes)
{
  int nn = 1, b = 0;
  void *r = 0;
  struct header *h;
  int c = mycpu()->id;

  while(nn < nbytes && b <= KMMAX){
    nn *= 2;
    b++;
  }
  if(nn != (1 << b))
    panic("kmalloc oops");
  if(b > KMMAX)
    panic("kmalloc too big");

  acquire(&freelists[c].lock);
  if(freelists[c].buckets[b] == 0)
    morecore(c, b);
  h = freelists[c].buckets[b];
  if(h){
    freelists[c].buckets[b] = h->next;
    r = h + 1;
    h->next = (header*) (long) b;
  }
  release(&freelists[c].lock);

  if (r)
    mtlabel(mtrace_label_heap, r, nbytes, "kmalloc'ed", sizeof("kmalloc'ed"));
  if(r == 0)
    cprintf("kmalloc(%d) failed\n", (int) nbytes);
  return r;
}

void
kmfree(void *ap)
{
  int c = mycpu()->id;
  struct header *h;
  int b;

  acquire(&freelists[c].lock);

  h = (struct header *) ((char *)ap - sizeof(struct header));
  b = (long) h->next;
  if(b < 0 || b > KMMAX)
    panic("kmfree bad bucket");

  verifyfree((char*) ap, (1<<b) - sizeof(struct header));
  if (ALLOC_MEMSET)
    memset(ap, 3, (1<<b) - sizeof(struct header));

  h->next = freelists[c].buckets[b];
  freelists[c].buckets[b] = h;
  mtunlabel(mtrace_label_heap, ap);
  release(&freelists[c].lock);
}

int
kmalign(void **p, int align, u64 size)
{
  void *mem = kmalloc(size + (align-1) + sizeof(void*));
  char *amem = ((char*)mem) + sizeof(void*);
  amem += align - ((uptr)amem & (align - 1));
  ((void**)amem)[-1] = mem;
  *p = amem;
  return 0;   
}

void kmalignfree(void *mem)
{<commit_msg>atomic (lockless) kmalloc<commit_after>//
// Allocate objects smaller than a page.
//

#include "types.h"
#include "mmu.h"
#include "kernel.hh"
#include "spinlock.h"
#include "kalloc.hh"
#include "mtrace.h"
#include "cpu.hh"

// allocate in power-of-two sizes up to 2^KMMAX
// must be < 12
#define KMMAX 11

struct header {
  struct header *next;
};

struct freelist {
  std::atomic<header*> buckets[KMMAX+1];
  char name[MAXNAME];
};

struct freelist freelists[NCPU];

void
kminit(void)
{
  for (int c = 0; c < NCPU; c++) {
    freelists[c].name[0] = (char) c + '0';
    safestrcpy(freelists[c].name+1, "freelist", MAXNAME-1);
  }
}

// get more space for freelists[c].buckets[b]
int
morecore(int c, int b)
{
  char *p = kalloc();
  if(p == 0)
    return -1;

  int sz = 1 << b;
  for(char *q = p;
      q + sz + sizeof(struct header) <= p + PGSIZE;
      q += sz + sizeof(struct header)){
    struct header *h = (struct header *) q;
    h->next = freelists[c].buckets[b];
    freelists[c].buckets[b] = h;
  }

  return 0;
}

void *
kmalloc(u64 nbytes)
{
  int nn = 1, b = 0;

  while(nn < nbytes && b <= KMMAX){
    nn *= 2;
    b++;
  }
  if(nn != (1 << b))
    panic("kmalloc oops");
  if(b > KMMAX)
    panic("kmalloc too big");

  scoped_gc_epoch gc;
  struct header *h;
  int c = mycpu()->id;

  for (;;) {
    h = freelists[c].buckets[b];
    if (!h) {
      if (morecore(c, b) < 0) {
        cprintf("kmalloc(%d) failed\n", (int) nbytes);
        return 0;
      }
    } else {
      if (cmpxch(&freelists[c].buckets[b], h, h->next))
        break;
    }
  }

  void *r = h + 1;
  h->next = (header*) (long) b;

  mtlabel(mtrace_label_heap, r, nbytes, "kmalloc'ed", sizeof("kmalloc'ed"));
  return r;
}

void
kmfree(void *ap)
{
  int c = mycpu()->id;
  struct header *h;
  int b;

  h = (struct header *) ((char *)ap - sizeof(struct header));
  b = (long) h->next;
  if(b < 0 || b > KMMAX)
    panic("kmfree bad bucket");

  verifyfree((char*) ap, (1<<b) - sizeof(struct header));
  if (ALLOC_MEMSET)
    memset(ap, 3, (1<<b) - sizeof(struct header));

  h->next = freelists[c].buckets[b];
  while (!cmpxch_update(&freelists[c].buckets[b], &h->next, h))
    ; /* spin */

  mtunlabel(mtrace_label_heap, ap);
}

int
kmalign(void **p, int align, u64 size)
{
  void *mem = kmalloc(size + (align-1) + sizeof(void*));
  char *amem = ((char*)mem) + sizeof(void*);
  amem += align - ((uptr)amem & (align - 1));
  ((void**)amem)[-1] = mem;
  *p = amem;
  return 0;   
}

void kmalignfree(void *mem)
{
{'fraction_non_alphanumeric': 0.19574216439976344, 'fraction_numerical': 0.013207175241474472, 'mean_word_length': 3.0952380952380953, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1827722', 'n_tokens_mistral': 2194, 'n_tokens_neox': 2098, 'n_words': 519}