On Wed, Jul 30, 2014 at 06:28:28PM -0400, John Snow wrote:

+#define bitany(X, MASK) ((X) & (MASK))
+#define bitset(X, MASK) (bitany((X), (MASK)) == (MASK))

This is subjective but macros like this should be avoided.  This macro does not
encapsulate anything substantial.  It forces the reader to jump to the
definition of this macro to understand the code, making code harder to read.

IMO a cleaner solution is to drop the macros:

  PCAllocOpts mask = PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT;
  if (s->opts & mask == mask) {                                 (1)
      if ((node->addr != s->start) ||
          (node->size != s->end - s->start)) {
          fprintf(stderr, "Free list is corrupted.\n");
          if (s->opts & PC_ALLOC_LEAK_ASSERT) {                 (2)
              g_assert_not_reached();
          }
      }
  }

Now that I read the expanded code, a bug becomes exposed:

In (1) we check that PC_ALLOC_PARANOID and PC_ALLOC_LEAK_ASSERT are both set.
Then in (2) we check whether PC_ALLOC_LEAK_ASSERT is set.  But we already knew
that PC_ALLOC_LEAK_ASSERT must be set in (1), so I guess the logic should have
really been:

  if (s->opts & (PC_ALLOC_PARANOID | PC_ALLOC_LEAK_ASSERT)) {
      if ((node->addr != s->start) ||
          (node->size != s->end - s->start)) {
          fprintf(stderr, "Free list is corrupted.\n");
          if (s->opts & PC_ALLOC_LEAK_ASSERT) {
              g_assert_not_reached();
          }
      }
  }

+#define MLIST_ENTNAME entries
+#define MLIST_FOREACH(node, head) QTAILQ_FOREACH((node), (head), MLIST_ENTNAME)
+#define MLIST_PREV(node) QTAILQ_PREV((node), MemList, MLIST_ENTNAME);
+#define MLIST_NEXT(node) QTAILQ_NEXT((node), MLIST_ENTNAME);

For the same reasons as my previous comment, please don't hide straightforward
expressions behind a macro.

+typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
+typedef struct MemBlock {
+    QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
+    uint64_t size;
+    uint64_t addr;
+} MemBlock;
 
 typedef struct PCAlloc
 {
     QGuestAllocator alloc;
-
+    PCAllocOpts opts;
     uint64_t start;
     uint64_t end;
+
+    MemList used;
+    MemList free;
 } PCAlloc;
 
-static uint64_t pc_alloc(QGuestAllocator *allocator, size_t size)
+static inline void mlist_insert(MemList *head, MemBlock *insr)
 {
-    PCAlloc *s = container_of(allocator, PCAlloc, alloc);
-    uint64_t addr;
+    QTAILQ_INSERT_HEAD(head, insr, MLIST_ENTNAME);
+}
+
+static inline void mlist_append(MemList *head, MemBlock *node)
+{
+    QTAILQ_INSERT_TAIL(head, node, MLIST_ENTNAME);
+}
+
+static inline void mlist_unlink(MemList *head, MemBlock *rem)
+{
+    QTAILQ_REMOVE(head, rem, MLIST_ENTNAME);
+}

For the same reasons as my comments about the macros, these trivial functions
are boilerplate.  Why not use the QTAILQ macros directly?

(It would be good to hide the list implementation if this was an external API
and you want to avoid exposing the implementation details, but within this
source file there is no point in extra layers of indirection.)