system - Where are UID for each application stored?

When installing an application, Android gives it an unique UID, which file(s) is used to keep track of used UIDs and to whom they belong? I want to forcibly change application UID to ensure they are the same on different device.

I've already checked with /data/system/packages.xml. But while that contains application permissions by package name, didn't see any UID there.

If it depends on Android version, for each versions superior or equal to 4.4.4 and source to documentation to figure it out myself for future versions.

Answer

You have already missed the correct answer.
The UIDs are stored right in /data/system/packages.xml, although an easier-to-interpret version with less information is available at packages.list.
Here's an example line of what's inside (scroll to the right)

jackpal.androidterm" codePath="/data/app/jackpal.androidterm-1" nativeLibraryPath="/data/app/jackpal.androidterm-1/lib" primaryCpuAbi="armeabi" flags="572996" ft="1592b6fa088" it="153d4948841" ut="158ed133c1f" version="71" userId="10001">

You see, there's a userId XML Attribute. This is exactly the UID you are asking for.
Furthermore, userId may be replaced by sharedUserId if an app shares its UID with another. Like (also scroll to right)

sharedUserId="1001">

Of course you don't want to go through that terribly long packages.xml, so you might want to take a look at packages.list, like

jackpal.androidterm 10001 0 /data/data/jackpal.androidterm default 3003,1028,1015

Very straight, isn't it? The 2nd field delimited with space is exactly the UID and it's the same as the one in packages.xml. Do not modify packages.list. All unmatching records in packages.list will be corrected from packages.xml.

Also, it's possible to change UID of an installed app if it does not have a shared UID. Simply edit packages.xml and reboot, then the new UID will have effect immediately. Old data will be erased for the changed app. If you want to keep data, apply chown recursively on the app's data directory in /data/data. If an app's old data gets erased by mismatching UID, related information will show up at /data/system/uiderrors.txt. Like this:

1970/01/01 00:00: Package jackpal.androidterm uid has changed from 0 to 10001, old data erased.

Tested on Android from 4 through 5. I guess this is applicable from Gingerbread to Nougat.