How should I implement a secure priority queue in C?

Question

I have an assignment to implement a priority queue in C as well as make an app that uses it. I, however, only know basic-level C (I do know Java). My intuition says that I need to learn pointers.

What other stumbling blocks should I expect or prepare for? How do I go about making this secure?

Answer 1

I want to say "not gonna happen". However, that wouldn't be very helpful, and perhaps not entirely accurate, either.

First of all, "security" is rather vague, but I think we can break it down:

• Be memory-safe. Don't allocate buffers that are too small, don't dereference wild pointers, don't overrun buffers, etc.

• Have good asymptotic complexity. Simply having an array of unsorted entries would require O(n) to pull out the item with the highest priority. Consider using a binary heap instead.

• Don't leak memory. Every call to malloc should have a corresponding call to free.

Second of all, learn enough C to work with data structures. I'll try to provide a quick overview:

struct

Define compound data types using the struct keyword. Example:

struct Foo
{
    int n[10];
};

structs are like classes in C++ or Java, but you can't embed methods directly in them.

When you use the type, you have to say struct Foo (C++ lets you leave off the struct, but not C). To avoid this inconvenience, consider using typedef:

typedef struct Foo Foo;

Pointers

Consider a binary tree node:

struct Node
{
    int value;
    struct Node *left;
    struct Node *right;
};

Here, left and right point to other Node structures. If we were to take out the asterisks:

struct Node
{
    int value;
    struct Node left;
    struct Node right;
};

Then it would mean left and right exist right here, in this object. That would require an infinitely large object! The compiler will refuse this code.

A pointer can be thought of as:

• A reference to another data structure

• A number representing a location in memory. Think of memory as a giant array of bytes. The operating system decides where to put things. A pointer is an index in that array.

Allocation

So how do we ask the operating system to reserve space for an object? We call malloc:

struct Node *node = malloc(sizeof(struct Node));

malloc reserves the requested number of bytes of memory, and returns a pointer telling us where those bytes are. It doesn't initialize the memory to anything, so it currently contains garbage.

sizeof computes the size of a data type (at compile-time).

We can also allocate things directly on the stack:

struct Node node;

As in the case of malloc, node will contain garbage. Here, node is a value. We can turn it into a pointer by using C's reference operator &:

struct Node *node_ptr = &node;

The advantages of allocating on the stack are:

• It's much faster than malloc

• It's freed automatically

The disadvantage is that node_ptr is invalid outside of the current scope. Thus, we can't return pointers to stack-allocated structures.

Accessing structures

The structure access operator in C is .:

struct Node node;
node.value = 42;

To access a structure value behind a pointer, we can combine the * (dereference pointer) and . (structure member) operators:

(*node).value = 42; /* . has higher operator precedence */

Better yet, use the shorthand -> operator:

node->value = 42;

Simple example

Here's an example program that defines a binary tree node and basic operations on it.

/* Needed for printf and perror */
#include <stdio.h>

/* Needed for malloc, free, and exit */
#include <stdlib.h>

typedef struct Node Node;

struct Node
{
    int value;
    Node *left;
    Node *right;
};

Node *node_new(int value, Node *left, Node *right)
{
    Node *node = malloc(sizeof(Node));

    if (node == NULL) {
        perror("node_new");
        exit(EXIT_FAILURE);
    }

    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

void node_delete(Node *node)
{
    if (node != NULL) {
        node_delete(node->left);
        node_delete(node->right);
        free(node);
    }
}

void node_dump(Node *node)
{
    if (node != NULL) {
        node_dump(node->left);
        printf("%d\n", node->value);
        node_dump(node->right);
    }
}

int main(void)
{
    Node *node =
        node_new(4,
            node_new(2,
                node_new(1, NULL, NULL),
                node_new(3, NULL, NULL)
            ),
            node_new(6,
                node_new(5, NULL, NULL),
                node_new(7, NULL, NULL)
            )
        );

    node_dump(node);
    node_delete(node);
    return 0;
}

Hope this helps.

Answer 2

I think it would be best you learn this (pointers et. al.) faster by doing than by trying to learn first.

here are some pointers:

1. A queue can be easily implemented in the form of linked list. So if you have a general idea of how linked lists (single or double) are created, by keeping a pointer for next (and previous) and update them appropriately, you are more or less done.

2. About priority essentially you need to keep some score (as say int) on each node, so whenever you insert the node you need to traverse till the point priority is less than the priority of new entrant node. Swap the next (previous) pointers of node appropriately.

3. About being secure, this is not very clear -but generally, to write secure code you must ensure that you do not carry finite buffers (pointers) without known lengths - and do not write data in any buffer which can potentially write down to unknown memory areas. This needs a great deal elaboration beyond the scope here.

Tips:

1. Do not forget to malloc each node before insertino, and free after removal (or usage).

2. Create a debug function - validate_all_nodes() and just traverse the entire list to see that all nodes are proper. Use this function every time you want to debug it.

Answer 3

If the set of priorities is small and virtual memory plentiful, it's a reasonable approach to use an array of queue structs, indexed by priority, where the consumer iterates the array from the high-priority end looking for a non-zero queue count. If the items queued are pointers, then a queue struct based on a 'classic' circular buffer with in/out indexes should be fine. If the priority queue is to be producer/consumer, then you need the usual pair of semaphores and a critical section, (or some other appropriate signaling/protection mechanism).

The advantages of this appoach is that it is not necessary to iterate a list, (or navigate a tree), of queued items on push/pop and also there is, in general, no malloc/free/realloc per push/pop, (ie. no contention on memory-manager either).

The memory-use issue can be mitigated by some extra code to malloc/realloc/free queue buffer space as necessary, but this obviously requires more code inside the queues lock, (especially if it is found that a queue needs to be realloced larger), impacting contention :(