Where is run_node defined in the sched_fair.c of Linux 2.6.33?

Question

I am reading Robert Love's Book Linux Kernel Development.

It uses the 2.6.33 kernel for demonstration.

I have been going through certain parts of the source and can't find out where is the initial definition of many things. A lot of things are just used, like "magic" without me finding the definition.

One example:

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);

    if (!last)
        return NULL;

    return rb_entry(last, struct sched_entity, run_node);
}

This is in kernel/sched_fair.c lines 384 and 394 in 2.6.33 kernel.

Where is the run_node coming from?

I have grep ed the entire source base over here, and I have not found any definition of run_node that would allow it to be used like this.

There is a declaration in the sched_entity structure, but nothing outside of it that would allow it to be used like this.

I cannot understand how things are organized, its really confusing.

What is going on?

Answer 1

The run_node you see is not a variable, it's the .run_node field of the sched_entity structure.

rb_entry() is a macro which is basically an alias for container_of():

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

The container_of() macro is used to get a pointer to a struct given a pointer to a known field (ptr), the structure type (type) and the field name (member). In your case left is a pointer to the run_node field of some struct sched_entity, so container_of() is basically used to get a pointer to the appropriate sched_entity.

See also: Understanding container_of macro in the Linux kernel.