@Pietry:
Well I see I was wrong about the million unique SIDs, it is indeed approx 65000.
I realised that the unique SID issue was the same one a filesystem faces when looking for a free block of space, so I went and looked at how they handle it. A bitmap is a common method, but doesn't scale well and, more importantly, is difficult to deal with in C# without using unsafe code. The method used by FAT et al is a list of blocks which handles both allocated and free space in the same list. Since this was overkill, your queue idea looked like the way to go, so I decided to implement it.
Initially it was using a bit more memory than I would have liked, but I realised that there was no point making the queue larger than the maximum number of allowed users, because there would still be a unique SID for everyone. This is my implementation:
Code: Select all
private void InitialiseSIDs()
{
// The size of this queue only really needs to be MAX_USERS, not 2^16.
// A Queue is a first-in, first-out (FIFO) collection implemented as a circular array.
// Objects are inserted at one end and removed from the other.
int limit = Settings.HubSettings.HubConnection.MaximumUsersCount < 65536 ? Settings.HubSettings.HubConnection.MaximumUsersCount : 65536;
_sids = new Queue<int>(limit);
for (int i = 0; i <= (limit - 1); i++)
{
_sids.Enqueue(i);
}
}
public static string GenerateNewSessionId(RemoteMachine.Node node)
{
string sidString = string.Empty;
bool creationSuccessful = false;
while (!creationSuccessful)
{
int newSid = _sids.Dequeue();
creationSuccessful = true;
sidString = Base32.Encode(BitConverter.GetBytes(newSid)).Substring(0, 4);
// by default, use ABCD for operator chat and DCBA for the security bot
if (sidString == Settings.HubSettings.OperatorBot.SessionId || sidString == Settings.HubSettings.SecurityBot.SessionId)
{
creationSuccessful = false;
continue;
}
}
_instance._clients[_instance._clients.IndexOf(node as RemoteMachine.Client)].SessionId = sidString;
return sidString;
}
internal static void RemoveDisconnectedClient(NetfractionHub.RemoteMachine.Node disconnectedClient)
{
_instance._clients.Remove(disconnectedClient);
_sids.Enqueue(BitConverter.ToUInt16(Base32.Decode(disconnectedClient.SessionId), 0));
}
Since the majority of hubs would only have a few hundred users, the average memory usage of this implementation turns out to be quite small, and the performance hit is shifted to a user disconnecting, where the SID must be re-queued, rather than a search through all existing users when somebody connects. The time spent to initialise the SIDs queue is negligible.
Thanks again to Pietry for this idea.
Storing the 20-bit number the SID is based on would obviously be more efficient for this purpose, but I still think it's going to use a lot of memory for such a very small part of the hub. I wonder if there's any useful computer science literature relating to this task... 
)