这个图是从 Machine 开始搜索的。要搜索的东西是 Test，每搜索到一个 Test 那么就会执行这个 Test，搜索的过程是 DFS 的。

The aim of qgraph is to create a graph of drivers, machines and tests.

device: interface in graph

A node can be of four types:

QNODE_MACHINE: for example arm/raspi2b
QNODE_DRIVER: for example generic-sdhci
QNODE_INTERFACE: for example sdhci (interface for all -sdhci drivers). An interface is not explicitly created, it will be automatically instantiated when a node consumes or produces it. An interface is simply a struct that abstracts the various drivers for the same type of device（注意是 same type of device，而不是某一个特定的 device）, and offers an API to the nodes that use it (“consume” relation in qgraph terms) that is implemented/backed up by the drivers that implement it (“produce” relation in qgraph terms).
QNODE_TEST: for example sdhci-test. A test consumes an interface and tests the functions provided by it.

What is produce and consume? 这都是针对于 interface node 而言的，一个 interface node 可以被 produce 也可以被 consume:

Produce：driver 会 produce interface（implement）
Consume：test 会 consume interface（use）

所以可以看出来，一个 interface 其实就是一个 API，这个 API 的被调用方是 driver 提供的，而调用者也就是 test。

Edge 有三种情况：

X CONSUMES Y: Y can be plugged into X，也就是说 X 是一个 test，Y 是一个 interface
X PRODUCES Y: X provides the interface Y，也就是说 Y 是一个 interface，X 是一个 driver
X CONTAINS Y: Y is part of X component，也就是说

The framework walks the graph starting from the available machines and performs a Depth First Search for tests

Command line is built by using node names and optional arguments passed by the user when building the edges.

There are three types of command line arguments:

in node : created from the node name. For example, machines will have -M <machine> to its command line, while devices (driver node) -device <device>. It is automatically done by the framework.
after node: added as additional argument to the node name. This argument is added optionally when creating edges, by setting the parameter after_cmd_line and extra_edge_opts in QOSGraphEdgeOptions.
- The framework automatically adds a comma before extra_edge_opts, because it is going to add attributes after the destination node pointed by the edge containing these options, and
- Automatically adds a space before after_cmd_line, because it adds an additional device, not an attribute.
before node : added as additional argument to the node name. This argument is added optionally when creating edges, by setting the parameter before_cmd_line in QOSGraphEdgeOptions. This attribute is going to add attributes before the destination node pointed by the edge containing these options. It is helpful to commands that are not node-representable, such as -fdsev or -netdev.

整个逻辑可以在下面函数中看到：

// tests/qtest/libqos/qgraph.c
qos_set_machines_devices_available
qos_graph_foreach_test_path

Qtest Driver Framework — QEMU documentation

Qgraph interface

Interface node 是在创建 edge 的时候自动创建的，请看函数 add_edge()。

QGraph edge `CONTAINS`

一个 machine node 会 contains driver node。说得通，因为一个 machine 上可能有多个 devices，所以是 contain 关系。

qos_node_create_machine("i386/pc", qos_create_machine_pc);
qos_node_contains("i386/pc", "i440FX-pcihost", NULL);

qos_node_create_machine("x86_64/pc", qos_create_machine_pc);
qos_node_contains("x86_64/pc", "i440FX-pcihost", NULL);

qos_node_create_driver("i440FX-pcihost", NULL);
qos_node_contains("i440FX-pcihost", "pci-bus-pc", NULL);

driver node 也可以 contain driver node：

static void qpci_generic_register_nodes(void)
{
    qos_node_create_driver("pci-bus-generic", NULL);
    qos_node_produces("pci-bus-generic", "pci-bus");
}

static void qpci_generic_pci_register_nodes(void)
{
    qos_node_create_driver("generic-pcihost", NULL);
    qos_node_contains("generic-pcihost", "pci-bus-generic", NULL);
}

// 第一个 driver contain 了第二个 driver
qos_node_contains("i440FX-pcihost", "pci-bus-pc", NULL);

下面两个函数也可以印证：

static void test_machine_contains_driver(void)
{
    check_machine(MACHINE_PC);
    check_driver(I440FX);
    check_contains(MACHINE_PC, I440FX);
}

static void test_driver_contains_driver(void)
{
    check_driver(PCIBUS_PC);
    check_driver(I440FX);
    check_contains(PCIBUS_PC, I440FX);
}

但是，为什么 check_contains 这个函数的参数一个是 machine，另一个就是 driver 呢？

static void check_contains(const char *machine, const char *driver)
{
    QOSGraphEdge *edge;
    qos_node_contains(machine, driver, NULL);

    edge = qos_graph_get_edge(machine, driver);
    g_assert_nonnull(edge);
    g_assert_cmpint(qos_graph_edge_get_type(edge), ==, QEDGE_CONTAINS);
    g_assert_cmpint(qos_graph_has_edge(machine, driver), ==, TRUE);
}

`struct QOSTestFunc` QEMU

函数签名是这样的：

typedef void (*QOSTestFunc) (void *parent, void *arg, QGuestAllocator *alloc);

`qos_add_test()` QEMU

添加一个 test node。

// name: test name
// interface，the interface we will consume
void qos_add_test(const char *name, const char *interface, QOSTestFunc test_func, QOSGraphTestOptions *opts)
{
    QOSGraphNode *node;
    char *test_name = g_strdup_printf("%s-tests/%s", interface, name);
    QOSGraphTestOptions def_opts = { };

    if (!opts) {
        opts = &def_opts;
    }
    // 创建一个 TEST 类型的 node，name 就是 test_name
    node = create_node(test_name, QNODE_TEST);
    // 把 function 挂到这里
    // 只有 test 类型的 node 才有 function。
    node->u.test.function = test_func;
    node->u.test.arg = opts->arg;
    //...
    node->u.test.before = opts->before;
    node->u.test.subprocess = opts->subprocess;
    node->available = true;
    // 因为一个 interface 会 consumed by 一个 test，而这种 consume 是一种边关系
    // 所以我们添加一个边来描述这种关系（interface, test_name）。
    // source node 是 interface，dst node 是 test_name
    // 如果没有这个 interface，那会自动创建一个 interface
    // 所以 interface 只有在创建节点的时候被创建。
    add_edge(interface, test_name, QEDGE_CONSUMED_BY, &opts->edge);
    //...
}

In-node command line

`build_machine_cmd_line()` QEMU

`build_driver_cmd_line()` QEMU

`tests/qtest/libqos/qgraph.c`

`libqos-malloc.c`

其实就是一个内存分配模拟器，并没有真正调用 malloc 来分配内存。而是模拟了内存分配的算法。用 free 和 used 两个数组来记录已经分配的内存和没有分配的内存。

`struct QGuestAllocator` QEMU

Guest 的内存分配器。

typedef struct QGuestAllocator {
    QAllocOpts opts;
    uint64_t start;
    uint64_t end;
    uint32_t page_size;

    // 一个关于 (addr, size) 的列表
    MemList *used;
    MemList *free;
} QGuestAllocator;

和 machine type 是相关的。比如说：

// x86
alloc_init(s, flags, 1 << 20, MIN(ram_size, 0xE0000000), ALLOC_PAGE_SIZE);
// arm-imx25-pdk
alloc_init(&machine->alloc, 0, IMX25_PDK_RAM_START, IMX25_PDK_RAM_END, ARM_PAGE_SIZE);
// arm-n800-machine
alloc_init(&machine->alloc, 0, N800_RAM_START, N800_RAM_END, ARM_PAGE_SIZE);
// arm-raspi2-machine
alloc_init(&machine->alloc, 0, RASPI2_RAM_ADDR + (1 << 20), RASPI2_RAM_ADDR + RASPI2_RAM_SIZE, ARM_PAGE_SIZE);
//...

pc_machine_register_nodes
    qos_create_machine_pc
        pc_alloc_init
            alloc_init

`alloc_init()` QEMU

初始化一个 QGuestAllocator。

void alloc_init(QGuestAllocator *s, QAllocOpts opts, uint64_t start, uint64_t end, size_t page_size)
{
    MemBlock *node;
    s->opts = opts;
    s->start = start;
    s->end = end;
    //...
    // 刚开始就这一个 node，node 的 size 就是整个 QGuestAllocator 的 size
    node = mlist_new(s->start, s->end - s->start);
    // 因为我们还没有分配任何内存，所以把这个 block 放到 free list 当中去。
    QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
    s->page_size = page_size;
}

`mlist_alloc()` QEMU

static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
{
    MemBlock *node;

    // 在 free list 里找到一部分空间
    node = mlist_find_space(s->free, size);
    if (!node) {
        // 没有空间了
        fprintf(stderr, "Out of guest memory.\n");
        g_assert_not_reached();
    }
    // 填上这部分空间
    return mlist_fulfill(s, node, size);
}

`mlist_fulfill()` QEMU

static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode, uint64_t size)
{
    uint64_t addr;
    MemBlock *usednode;

    g_assert(freenode);
    g_assert_cmpint(freenode->size, >=, size);

    addr = freenode->addr;
    // 大小正好相等
    if (freenode->size == size) {
        QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
        usednode = freenode;
    } else {
        // 原来 free 的 node 会缩小
        // 是从 free node 开始的那部分空间分配的。
        freenode->addr += size;
        freenode->size -= size;
        usednode = mlist_new(addr, size);
    }

    mlist_sort_insert(s->used, usednode);
    return addr;
}

`guest_alloc()` QEMU

让 Guest 分配指定大小的内存区域。会返回分配到的内存的起始地址。

uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
{
    uint64_t rsize = size;
    uint64_t naddr;

    //...
    // 按 page size 大小来分配
    rsize += (allocator->page_size - 1);
    rsize &= -allocator->page_size;
    // 整个 guest 的 mem 大小应该能够涵盖这个 size。
    g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
    // page-align 后的 size 一定要大于传入的 page size。
    g_assert_cmpint(rsize, >=, size);

    // 
    naddr = mlist_alloc(allocator, rsize);
    // 类似妄想狂的；属于偏执狂的
    // 类似于强迫症必须要检查一下？
    if (allocator->opts & ALLOC_PARANOID)
        mlist_check(allocator);

    return naddr;
}

Qgraph interface

QGraph edge CONTAINS

struct QOSTestFunc QEMU

qos_add_test() QEMU

In-node command line

build_machine_cmd_line() QEMU

build_driver_cmd_line() QEMU

tests/qtest/libqos/qgraph.c

libqos-malloc.c

struct QGuestAllocator QEMU

alloc_init() QEMU

mlist_alloc() QEMU

mlist_fulfill() QEMU

guest_alloc() QEMU