These two lines should be moved after the license. The license should be strictly as suggested here:

https://www.freebsd.org/doc/en/articles/committers-guide/pref-license.html

Instead of this, you can just add $FreeBSD$ in the comment, after the license.

To be clear, the lines before the copyright line are what should be moved, not the copyright line.

For .c files, this is the correct way. For .h files, you are correct.

Hmm.. then I guess I have screwed up more than once :(.

The bracket should be on the same line as the iterator.

Same here, this should be on the same line as the if (there are a bunch of those, so I'm going to stop commenting on each one of them).

Would it be better to use a red-black tree in order to store the list of grants from a performance point of view? I expect that the list is going to be mostly accessed in order to search for granted regions rather than adding or removing them.

There's an example of a red-black tree usage in sys/vm/vm_phys.c, search for the RB_* macros :).

So you do the cleanup of expired grefs when new ones are mapped, shouldn't it be better to defer the cleanup to some background task, so that it doesn't interfere with the allocation of new grefs? Take a look at the TASKQUEUE(9) man page, it allows to schedule asynchronous task execution.

gref cannot be NULL, because you are suing M_WAITOK, so you can remove this check (or turn it into a KASSERT if you are paranoid :))

Same here, you should probably look into making gref_list_dtor a task that you can schedule in the background, because AFAICT there's no obvious reason that it should be explicitly done at this point.

You should not declare variables here, instead do it at the top of the function (didn't you get a complain from the compiler here?)

No need for the brackets here.

gref == NULL (gref is not a boolean, so you should not use !).

malloc with M_WAITOK cannot fail (there are a couple more below which I'm not going to comment on).

Why do you need to set handle to -1 and host_addr to 0, aren't you just unmapping the grants?

It seems like indentation is off here, but maybe it's just phabricator. Could you make sure you indent the lines that you have to break (because they are too long) using 4 spaces.

Don't mix declarations with code, this should be declared at the beginning of the function.

All the cases are indented one level more than required. "switch" and "case" should be at the same indent level.

You should create two separate helpers here, one for the gnt map and one for the gnt share cases, in order to help the readability of the code.

This comments (here and below) don't follow the coding style, check style(9).

If the function doesn't have any local variables an empty newline should be left at the top (here and below).

Hm, why did you add this C++ compat thing? None of the FreeBSD headers for Xen user-space devices have it AFAIK.

It might be an overkill, given that we access the list only twice or thrice for every allocated grant (mmap, maybe notify, and dealloc). Linux uses a list.

I guess it should be rare that some domain keeps an allocated grant mapped, even when access from this side has ended. This function is always called when any grant is deallocated, but just to kill phantom grants still alive, I call it here.
Linux also calls it, but I guess their reasons are different, they want to ensure max number of free grants are available before the allocation happens.

Since this is an error, mostly only free() calls will happen here.

This function might be called in case the Map Hyper-call fails partially (say half of the grants are mapped and the rest are not) (line 924). In that case, I enumerate over the successful maps, and un-map them. Since the user can retry the mmap in such a case, to redo the hyper-call, I update the internal data-structures to represent the fact that none of the grants are mapped anymore. After this, the state of the internal data structures is same as it was before the mmap had happened.

I've removed it. It's the default template for C header files on my system. It's not required here, as we just have structure definitions, and even if there were any declarations, I guess the kernel doesn't have any C++ code that would require this.

With the addition of the RB tree now the structure requires two different handlers, one for the RB tree and another one for the TAILQ, which is rather unfortunate (also taking into account that there might be hundreds of those on a busy Dom0.

Could you please benchmark if the usage of the RB tree makes any difference from a performance point of view?

In order to test it you should create a NULL memdisk (all reads will return 0, writes are ignored) using:

# mdconfig -a -t null -s 10g

Attach it to a guest using the Qdisk backend and then run fio (or any other disk benchmark) against the raw block device. You should test the pre-RB and the RB versions of the gnttab device and decide if the addition of the RB tree is worth it or not.

Since this now runs in a taskqueue you should use a STAILQ list, and only hold the mutex in order to pick the first element from the queue and remove it. The unmap and cleanup should be done without holding the mutex in order to prevent contention. If the element can not be removed you will have to put it into a local queue that will be appended to the global one once processing has finished. You will have to do it that way in order to prevent iterating forever over grants that cannot be unmapped.

Great, it looks marginally better.

FWIW, in FreeBSD (and other projects), when you give performance figures you usually have to use a table of some sort, with the relevant data, and the stddev. Without this data results could be considered useless. If you want to give this a try, there's a very good cli tool in FreeBSD called 'ministat(1)', that will give you a nice graph and will tell you whether there's a performance benefit or it's just an statistic illusion. IMHO it's not necessary in this case, but I would recommend that you give it a try if you want/can.

In order to reduce the size of this struct, you should put gref_list_next and gref_tree_next inside of a union, since AFAICT, you will never have a gref added to both the cleanup tree and a RB tree (same applies to gntdev_gmap).

And the struct definitions should all be at the top of the file. Having functions interleaved with struct definitions makes the code harder to read IMHO (I might be convinced otherwise if you think it's better the other way around).

I don't see any reason for this ioctl to exists, it's not implemented and will never be. Should be removed from the header too.

Yes. The check is already present.
The check is done when choosing the gmap/gref to make the notify structure into. Line 840-841 for gmap, and function call to gntdev_find_grefs(.., index, ..) at line 829 for gref.

Now that I look again into this, isn't this a little bit too simplistic? At some point priv_user->file_offset is going to overflow, returning into 0, and then we risk overlapping with existing regions. IMHO, you should use something like a region manager (rangeset), that can keep track of start and sizes of the allocated regions, it's going to add a little bit more of logic, but at least we will be on the safe side.

Aye Aye! This was an improvement I left on for something later. (Linux uses similar simplistic logic for alloc, but perhaps something more complicated for map).
Since, we now have time, I'll look into the rangeset. :)