Skip to content

Buddy Memory Allocation

A regularly used method for allocating space within a fixed region is Buddy Memory Allocation. This system works like a tree, where each branch either has a boolean value or branches to another set of the same.

8
44
2222
11111111
This means that when you allocated large chunks, or there are multiple chunks allocated next to each other they can merge branches into a single value of true, thus saving memory and compute time since there is no point testing all of the branches if it is already know that they are all true. --- ## Defining First of all, we need to set up a branch class since we will have any interlinking entities of this structure and behaviour. **A** & **B**: Are both branches of the current fork ``BMA``. **Size**: Is the area of which each sub-branch will cover. 
class BMA{
  constructor(parent = null, size = 8){
    this.parent = parent;
    this.a = false;
    this.b = false;
    this.size = size;
  }

  get(start, end){}
  set(start, end){}

  merge(target){}

  find(val, length){}
}
## Defining First of all, we need to enforce a boolean type to value, as well as calculation the actual size of the allocation being requested. 
set(start, end){
  val = (val == true);
  let size = e - s;

  //...
If the value will overwrite an entire branch then, all we need to do is set the branch value to ``val``. Also if this change makes both branches the same, then there is no point in the divide existing, so we should tell the parent that this path should just be ``val``. 
  //...

  //Fills sect A
  if (s == 0 && e == this.size){
    this.a = val;

    // There is no reason for this branch to exist anymore
    if (this.b == val && this.parent){
      this.parent.merge(this);
    }

    //End execution since the desired section only fills this space.
    return this;
  }

  //Fills sect B
  if (s == this.size && e == this.size + this.size){
    this.b = val;
    if (this.a == val && this.parent){
      this.parent.merge(this);
    }

    return this;
  }

  //...
Now we need to handle the complex issues of when a request only partly fills a part of a branch/s. We need to test if the request is touching each branch, and then cascade the set operation down the tree until it completely fills a section/s. We also need to keep in mind what the branches previous value was because that is what all new subsequent branches value should be unless it is overwritten by the new set operation. 
  //...

  // Collides with sect A, and is changing a value
  if (s < this.size && this.a != val){
    if (!(this.a instanceof BMA)){
      let was = this.a;
      this.a = new BMA(this, this.size/2); // Create a new sub branch
      this.a.a = this.a.b = was; // Apply the old value to the default value of the new branches
    }

    // Confine the range to fit within the sub-branch, and parse the value down the tree.
    this.a.set(s, Math.min(this.size, e), val);
  }

  // Collides with sect B, and is chaning a value
  if (e > this.size && this.b != val){
    s -= this.size;
    e -= this.size;

    if (!(this.b instanceof BMA)){
      let was = this.b;
      this.b = new BMA(this, this.size/2);
      this.b.a = this.b.b = was;
    }

    this.b.set(Math.max(0, s), e, val);
  }

  //...
Now we just need a final check to run to make sure that if this set caused merging of branches, that it actually continues it's way up the tree. 
  //...

  if (this.parent && this.a==this.b){
    this.parent.merge(this);
  }

  return;
}
--- ## Getting There is no point to define anything if you can't read the information back. Since the request can expose a large section of the allocation information it means that the total value over the range can be a mix of true and false. Thus instead of returning true and false from this function, we will instead return 1, and -1, respectively, using 0 to mean that the area is a mix of both. When the request is entirely within only one section. 
get (s, e){

  // Only in sect A
  if (s < this.size && e <= this.size){
    // If a is another branch, then parse forward the request
    if (this.a instanceof BMA){
      return this.a.get(s, e);
    }

    // If a is true return 1, else return -1
    return this.a ? 1 : -1;
  }

  // Only in sect B
  if (s > this.size){
    if (this.b instanceof BMA){
      return this.b.get(
        s-this.size, //Make the pointers relative
        e-this.size
      );
    }

    return this.b ? 1 : -1;
  }

//...
Now we need to write a case for if the request covers at least some of both branches. This means we need to test the composition of which covers each branch, and if the two values don't match then return 0, otherwise we can just return their shared value. > Remember, if one branch is a mix of both values there is no point in testing the value of the other since any possible combination will also just result in a mix of the two. 
//...

  let a = null;
  let b = null;

  // If the request collides with branch A
  if (s < this.size){
    if (this.a instanceof BMA){
      a = this.a.get(
        s,
        Math.min(this.size, e) // Ensure that the parsed end pointer isn't going out of the branch
      );
    }else{
      a = this.a ? 1 : -1;
    }

    if (a === 0){
      return 0;
    }
  }

  // If the request collides with branch B
  if (e > this.size){
    if (this.b instanceof BMA){
      b = this.b.get(s-this.size, e-this.size);
    }else{
      b = this.b ? 1 : -1;
    }

    if (b === 0){
      return 0;
    }
  }



  // If one of the branches's didn't actually collide with the request
  if (a === null){
    return b;
  }
  if (b === null){
    return a;
  }

  if (a === b){
    return a;
  }else{
    return 0;
  }

}
--- ## Finding space There is no point to an allocation system if you can't find a space to put some data. So our request will just state the desired size. We will also make this function more versatile by allowing the request to specify the value it is trying to find, and thus how much space that value takes up. We also should always make sure that we return the tightest fitting space available because then it allows the bigger available spaces to be filled by future requests. 
hit (val, size){
  // The request won't fit, at this depth, so there's no point
  // Checking deeper branches since they will just have less
  // space
  if (this.size < size){
    return NaN;
  }

  // If the request matches an available branch
  if (this.a === val){
    return {pos: 0, size: this.size}
  }else if (this.b === val){
    return {pos: this.size, size: this.size}
  }


  let a = NaN;
  let b = NaN;
  if (this.a instanceof BMA){
    a = this.a.hit(val, size);

    // Tight fit found
    // There will be no better solutions, only equal best
    if (a != NaN && a.size == size){
      return a;
    }
  }
  if (this.b instanceof BMA){
    b = this.b.hit(val, size);

    if (b != NaN && a.size == size){
      return b;
    }
  }


  // If an option is NaN, then return the other option
  let na = isFinite(a) && isNaN(a);
  let nb = isFinite(b) && isNaN(b);
  if (na && nb){
    return NaN;
  }
  if (!na && nb){
    return a;
  }
  if (na && !nb){
    return b;
  }

  // Both options a & b will work,
  // Select which ever one is smallest,
  // Prioritising a
  if (a.size < b.size){
    return a;
  }
  if (b.size > a.size){
    b.pos += this.size; // Make the pos relative to this depth
    return b;
  }
  if (a.size === b.size){
    return a;
  }

  throw new Error()
}
However, this allocation system doesn't automatically example it's self when necessary to write new data. This will add a new parent class to allow this. 
class BMAX{
  constructor(length){
    this.root - new BMA();
    this.length = this.root.size *2;
  }

  set (s, e, val){
    return this.root.set(s,e,val);
  }
  get (s,e){
    return this.root.get(s,e);
  }
  find(size, val){
    return this.root.hit(val === true, size);
  }

  extend(amount = 1){
    let ol = this.length;
    if (amount < 1){
      amount = 1;
    }

    // Make the current root into a branch of a new root
    while(this.length - ol < amount){
      let t = new BMA(undefined, this.length);
      t.a = this.root;
      t.a.parent = t;
      this.root = t;

      this.length = this.root.size*2;
    }
  }
}
Now if the recursive search function doesn't return any results, we can tell the allocation table to expand, as well as expanding out initial storage location to now have space to put the new data. --- [code](https://github.com/Hobgoblin101/Hobgoblin101.github.io/tree/master/code/9)