[TASKS] Report for Project: radix tree __alloc_fd

[Rehas Sachdeva <aquannie@gmail.com>]

Reporting my findings for the Project:

radix tree __alloc_fd

Task 1:
Read how sys_open() currently finds the first open file descriptor, and
allocates/resizes the file descriptor table.

The sys_open call has its prototype definition in include/linux/syscalls.h.

asmlinkage long sys_open(const char __user *filename, int flags, umode_t mode);

It takes in the name/path of the file to open, a mask to denote whether it's
read-only, write-only, append mode etc, and a mask to specify the permissions.
It returns a small, non-negative integer as the file descriptor of the file
opened, or -1 in case of error.

It further calls:

long do_sys_open(int dfd, const char __user *filename, int flags, umode_t mode)

with dfd = AT_FDCWD, i.e. to assume current working directory in case of
relative path. 

For the purpose of finding first available file descriptor, it calls:

int get_unused_fd_flags(unsigned flags)

which calls:

int __alloc_fd(struct files_struct *files,
      unsigned start, unsigned end, unsigned flags)

This looks at fdtable object current->files->fdtab (fdt). Next it callls

find_next_fd(fdt, files->next_fd)

fdt->open_fds is a bitmap which tells us the set bits corresponding to open
fds. The call find_next_zero_bit(fdt->open_fds, maxfd, start) finds the next
available fd by checking the next zero bit from the fdt->open_fds bitmap, whose
max size is maxfd, and starting from the offset start which corresponds to
files->next_fd.

After this expand_files(files, fd) is called. If the requested size (fd) exceeds
the current capacity and there is room for expansion, it calls
expand_fdtable(files, fd).

This allocates memory for new_fdt and marks its fields max_fds, open_fds,
full_fds_bits according to new required capacity. 

The call copy_fdtable(new_fdt, cur_fdt) which allocates the new size to the fd
array and copies all the bitmaps from cur_fdt (corresponding to already open
fds) to new_fdt.

We repeat the procedure from __alloc_fd in case the call to expand_files needed
to expand fd array and it resulted in a block. Otherwise we update the
fdt->open_fds (__set_open_fd(fd, fdt)) and return the allocated fd.

This linear search through a bitmap can also be achieved by the IDR interface,
which can replace some custom code in the kernel with generic code (hopefully
shrinking the size of the kernel), could result in some memory savings for
processes with relatively few open files, and hopefully improve performance of
workloads with very large numbers of open files.

Task 2:
Understand the IDR API

IDR API is charged with the allocation of integer ID numbers used with device
names, POSIX timers, and more.

	int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
	int idr_get_new(struct idr *idp, void *ptr, int *id);

The call to idr_pre_get() performs all the memory allocations necessary to
ensure that the following call to idr_get_new() (which returns the newly
allocated ID number and associates it with the given ptr) is able to succeed.

Looking up an existing ID is achieved with:
	void *idr_find(struct idr *idp, int id);
The return value will be the pointer associated with the given id, or NULL
otherwise.

To deallocate an ID, use:
    void idr_remove(struct idr *idp, int id);

With these functions, kernel code can generate ID numbers to use as minor
device numbers, inode numbers, or in any other place where small integer IDs
are useful, for instance file descriptors.

Timeline for project - Radix tree __alloc_fd:
- Get a deeper understanding of __alloc_fd implementation, and also IDR api
implementation and clear any doubts about it.(1-2 weeks)
- Implement a sample usage of the IDR api to achieve the basic functionality of
the search for next fd by the __alloc_fd. (1-2 weeks)
- Integrate the IDR api to the __alloc_fd functionality and make required
changes to __alloc_fd according to the new functionality (2-3 weeks).
- Document the changes. Report the decrease in size of kernel code and
performance improvement, and memory savings. (1 week)
- Any other cleanups/refactoring/modifications required to the code
implemented. (1-2 weeks).
- Buffer time for unexpected delays, or necessary work unidentified in the
beginning. (1-2 weeks).

Thanks a lot!

Rehas