2008/2009 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 3
Dark Storage Finder

Modern data centers often use large storage arrays to hold the storage used by the servers. The arrays take a set of physical disk drives, remap them to LUNs (logical units), then present those LUNs to the servers. To the server operating system, these LUNs appear to be disk drives that are connected to the server, in the same way that physical drives connected directly by cables do. The storage arrays can present logical units of arbitrary sizes, provide built-in redundancy for reliability, and provide other advanced storage management features.
There are several protocols that can be used between servers and storage arrays, but the most common at present is Fibre Channel. A server has one or more Fibre Channel Host Bus Adapter (HBA) ports that connect to Fibre Channel switch(es). An array also has one or more (usually several) Fibre Channel ports that connect to the switches. Logical paths between the servers and arrays are defined in the switches-these paths are known as zones.
An array has LUNs of varying sizes defined on it, and these LUNs are presented to specific servers using specified Fibre Channel ports on the array. A LUN may be presented to more than one server.
Server and array Fibre Channel ports are identified by their "Port World Wide Name" (PWWN). A PWWN is a globally-unique 64-bit address. A server sees the PWWNs of the arrays it uses storage on; the array sees the PWWNs of the servers that connect to it. The server PWWNs are used to define which servers have access to each LUN.
Over time, servers are added and removed from large data centers. The storage administrators are certainly notified when servers are added so they can create and allocate new LUNs-but they are not necessarily notified when servers are removed or server configurations change. This means that there may be storage on an array that is configured but not actually in use ("dark" or "stranded" storage). It is not unheard of for terabytes of storage to be stranded in large data centers.
There are commercial tools that cost thousands of dollars to help find this storage (among other features). However, in the interest of saving money, the management of one such data center has decided to ask programming contest teams to develop a tool to find stranded storage instead.
The relationships between the storage array LUNs, the servers, and the switches are defined in pairwise relationships:
·
A LUN is mapped to a storage port (possibly more than one)
·
A LUN is masked to a server HBA (possibly more than one)
·
A storage port has a PWWN
·
A server has one or more server HBAs, each with a PWWN
·
A switch zone connects a storage PWWN to a server HBA PWWN (a given storage PWWN may be zoned to multiple server HBA PWWNs, and a given server HBA PWWN may be zoned to multiple storage PWWNs)
·
A server file system resides on a LUN or logical volume (a LUN may hold multiple server file systems)
·
A server logical volume uses one or more LUNs
These relationships are defined on a series of input lines for your program. Each line describes one relationship as described below. Words in uppercase appear literally in the input. Elements on a line are separated from each other by one or more spaces. A line may contain leading and/or trailing spaces. No input line is longer than 80 columns. Relationships can appear in any order in the input. There will be no more than 3000 relationships.


 
LUNMAP  < Array ID >   < LUN ID >   < Port ID > 
LUNMASK  < Array ID >   < LUN ID >   < Server PWWN > 
ARRAYPORT  < Array ID >   < Port ID >   < Port PWWN > 
ZONE  < Port PWWN >   < Server PWWN > 
SERVERHBA  < Server name >   < Server PWWN > 
SERVERFS  < Server name >   < File system name >  LUN  < Array ID >   < LUN ID > 
SERVERFS  < Server name >   < File system name >  LV  < Logical volume name > 
SERVERLV  < Server name >   < Logical volume name >   < Array ID >   < LUN ID > 

Each array ID, port ID, server name, file system name, and logical volume name is a string of one to twenty alphanumeric characters. Case is significant.
A server HBA or port PWWN is a 64-bit value expressed as eight pairs of hexadecimal digits separated from each other by colons (for example, 01:23:45:67:89:AB:CD:EF). Case is not significant.
A LUN ID is a hexadecimal value from 0 to FFFF16. Case is not significant. The same LUN ID value may be used on different storage arrays.
For a storage LUN to be used, it must be mapped to a storage port, masked to one or more HBAs on one or more servers, connected with one or more zones between the storage port(s) and the server(s), and then used on one or more file systems. A server file system may reside directly on a LUN or use a logical volume that is made up of one or more LUNs.
Your program is to read a set of descriptions as defined above and determine which storage LUNs are defined in LUN mapping or masking entries but are not actually in use.
Your program should produce a list of the "dark" unused LUNs, one per line. The list should be sorted by array name in ASCII order, and within an array, by increasing hexadecimal LUN value. Each line should contain the array name starting in the first column, followed immediately by a colon and the four-digit hexadecimal LUN number (including leading zeroes, with the values A-F in upper case). No trailing whitespace is to appear on an output line.


Sample Input
LUNMAP S6 1 C1
LUNMAP S6 2 C1
LUNMAP CX 10 SPA0
LUNMAP CX 11 SPA0
LUNMAP CX 10 SPB0
LUNMAP CX 11 SPB0
ARRAYPORT S6 C1   20:00:00:10:00:0A:00:C1
ARRAYPORT CX SPA0 50:06:00:60:00:00:00:00
ARRAYPORT CX SPB0 50:06:00:68:00:00:00:00
 SERVERHBA PRD1    10:00:00:00:C9:01:00:01
 SERVERHBA PRD2    10:00:00:00:C9:01:01:01
 SERVERHBA PRD2    10:00:00:00:C9:01:01:02
LUNMASK S6 1      10:00:00:00:C9:01:00:01
LUNMASK S6 1      10:00:00:00:C9:02:00:01
LUNMASK S6 2      10:00:00:00:C9:02:00:01
 ZONE  20:00:00:10:00:0a:00:C1   10:00:00:00:C9:01:00:01
 ZONE  50:06:00:60:00:00:00:00   10:00:00:00:C9:01:01:01
 ZONE  50:06:00:68:00:00:00:00   10:00:00:00:C9:01:01:02
LUNMASK CX 10     10:00:00:00:C9:01:01:01
LUNMASK CX 11     10:00:00:00:C9:01:01:01
LUNMASK CX 10     10:00:00:00:C9:01:01:02
LUNMASK CX 11     10:00:00:00:C9:01:01:02
SERVERFS PRD1 tempdb LUN S6 1
SERVERFS PRD1 scratchfs LUN S6 2
SERVERFS PRD2 bigsas LV SASLV
SERVERLV PRD2 SASLV CX 11


Output for the Sample Input

CX:0010
S6:0002





File translated from TEX by TTH, version 3.77.
On 20 Nov 2008, 20:33.