[CRIU] Re: [PATCH 10/10] files: Use sys_kcmp to find file descriptor duplicates

[Pavel Emelyanov]

> +static struct fd_id_entry *
> +lookup_alloc_subtree(struct fd_id_entry *e, u64 genid, pid_t pid, int fd)

OK, I like the overall idea. It should be written on wiki as a separate page,
and a summary comment should be put here.

> +{
> +       struct rb_node *node = e->subtree_root.rb_node;
> +       struct fd_id_entry *sub = NULL;
> +
> +       struct rb_node **new = &e->subtree_root.rb_node;
> +       struct rb_node *parent = NULL;
> +
> +       while (node) {
> +               struct fd_id_entry *this = rb_entry(node, struct fd_id_entry, subtree_node);
> +               int ret = sys_kcmp(this->pid, pid, KCMP_FILE, this->fd, fd);
> +
> +               parent = *new;
> +               if (ret < 0)
> +                       node = node->rb_left, new = &((*new)->rb_left);
> +               else if (ret > 0)
> +                       node = node->rb_right, new = &((*new)->rb_right);
> +               else
> +                       return this;
> +       }
> +
> +       sub = alloc_fd_id_entry(genid, pid, fd);
> +       if (!sub)
> +               goto err;
> +
> +       sub->subid = fd_id_entries_subid++;
> +
> +       rb_link_node(&sub->subtree_node, parent, new);
> +       rb_insert_color(&sub->subtree_node, &e->subtree_root);

Same code in the below function. Merge them.

> +err:
> +       return sub;
> +}
> +
> +static struct fd_id_entry *
> +lookup_alloc(u64 genid, pid_t pid, int fd)
> +{
> +       struct rb_node *node = fd_id_root.rb_node;
> +       struct fd_id_entry *e = NULL;
> +
> +       struct rb_node **new = &fd_id_root.rb_node;
> +       struct rb_node *parent = NULL;
> +
> +       while (node) {
> +               struct fd_id_entry *this = rb_entry(node, struct fd_id_entry, node);
> +
> +               parent = *new;
> +               if (genid < this->genid)
> +                       node = node->rb_left, new = &((*new)->rb_left);
> +               else if (genid > this->genid)
> +                       node = node->rb_right, new = &((*new)->rb_right);
> +               else
> +                       return lookup_alloc_subtree(this, genid, pid, fd);
> +       }
> +
> +       e = alloc_fd_id_entry(genid, pid, fd);
> +       if (!e)
> +               goto err;

Here the subid will be INVALID. This is ... wrong.

> +       rb_link_node(&e->node, parent, new);
> +       rb_insert_color(&e->node, &fd_id_root);
> +err:
> +       return e;
> +}
> +
> +struct fd_id_entry *fd_id_entry_collect(u64 genid, pid_t pid, int fd)
> +{
> +       return lookup_alloc(genid, pid, fd);

:\

> +struct fd_id_entry {
> +       struct rb_node  node;
> +
> +       struct rb_root  subtree_root;
> +       struct rb_node  subtree_node;
> +
> +       u64             genid;  /* generic id, may have duplicates */
> +       u64             subid;  /* subid is always unique */
> +
> +       pid_t           pid;
> +       int             fd;
> +} __aligned(sizeof(long));
> +
> +/* Position in file is u64 so we can't shrink it */
> +#define MAKE_FD_GENID(dev, ino, pos) \
> +       ((u64)(dev) ^ (u64)(ino) ^ (u64)(pos))

Since genid is just a hint, we can make it 32bit and just trim the pos.
So can we make subid be 32 bit and ...

>  struct fdinfo_entry {
>         u8      type;
>         u8      len;
>         u16     flags;
>         u32     pos;
>         u64     addr;
> -       u8      id[FD_ID_SIZE];
> +       u64     genid;
> +       u64     subid;

... make this a single 64bit ID field.

>         u8      name[0];
>  } __packed;