title: explanation to aligned malloc implementation
body: <p>This is not homework, this is purely for my own personal education.</p>
  
  <p>I couldn't figure out how to implement an aligned malloc so looked online and found <a href="https://sites.google.com/site/ruslancray/lab/bookshelf/interview/ci/low-level/write-an-aligned-malloc-free-function" rel="noreferrer">this website</a>. For the ease of reading I will post the code below:</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  
  void* aligned_malloc(size_t required_bytes, size_t alignment)
  {
      void* p1; // original block
      void** p2; // aligned block
      int offset = alignment - 1 + sizeof(void*);
      if ((p1 = (void*)malloc(required_bytes + offset)) == NULL)
      {
         return NULL;
      }
      p2 = (void**)(((size_t)(p1) + offset) &amp; ~(alignment - 1));
      p2[-1] = p1;
      return p2;
  }
  
  void aligned_free(void *p)
  {
      free(((void**)p)[-1]);
  }
  
  void main (int argc, char *argv[])
  {
      char **endptr;
      int *p = aligned_malloc (100, strtol(argv[1], endptr, 10));
  
      printf ("%s: %p\n", argv[1], p);
      aligned_free (p);
  }
  </code></pre>
  
  <p>The implementation does work, but I honestly can't figure out how it works.</p>
  
  <p>Here is what I can't understand:</p>
  
  <ol>
  <li>Why we need an offset?</li>
  <li>What does anding with <code>~(alignment - 1)</code> accomplish</li>
  <li><code>p2</code> is a double pointer. How come we can return it from a function that is supposed to return only a single pointer?</li>
  <li>What is the general approach to solve this problem?</li>
  </ol>
  
  <p>Any help is really appreciated.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>This is not a duplicate of <a href="https://stackoverflow.com/questions/227897/how-to-allocate-aligned-memory-only-using-the-standard-library">How to allocate aligned memory only using the standard library?</a> because I also need to know how to free aligned memory.</p>