IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`US006161111A
`[11] Patent Number:
`[45] Date of Patent:
`
`6, 161, 111
`Dec. 12, 2000
`
`5, 893, 140
`5, 948, 062
`5, 950, 203
`
`4/1999 Vahalia et al.
`9/1999 Tzelnic et al.
`9/1999 Stakuis et al.
`
`711/118
`. . . . 707/10
`. . . . 707/10
`
`Pvimavy Examiner — Wayne Amsbury
`Assistant Examiner — Thu-Thao Havan
`Attorney, Agent, or Firm~ichard A. Jordon; John M.
`Gunther
`
`United States Patent
`Mutalik et al.
`
`[19]
`
`[54] SYSTEM AND METHOD FOR PERFORMING
`FILE-HANDLING OPERATIONS IN A
`DIGITAL DATA PROCESSING SYSTEM
`USING AN OPERATING
`SYSTEM-INDEPENDENT FILE MAP
`
`[75]
`
`Inventors: Madhav Mutalik, Northboro; Faith M.
`Senie, Bolton, both of Mass.
`
`[73] Assignee: EMC Corporation, Hopkinton, Mass.
`
`[21] Appl. No. : 09/052, 356
`Mar. 31, 1998
`[22] Filed:
`[51] Int. Cl.
`[52] U. S. Cl. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`G06F 17/30
`707/205; 707/10; 711/118;
`705/42
`[58] Field of Search
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707/205, 10, 8;
`705/42; 364/242, 400; 711/118; 713/165;
`700/94
`
`[56]
`
`References Cited
`U. S. PATENT DOCUMENTS
`
`5, 321, 816
`6/1994 Rogan et al.
`9/1995 Myers et al. .
`5, 454, 099
`5, 881, 311 3/1999 Wood
`
`. . 705/42
`. . . . 714/6
`. 710/4
`
`[57]
`
`ABSTRACT
`
`A file management
`is disclosed for managing
`files
`system
`to file
`stored on a mass storage
`subsystem
`in response
`management commands. The mass storage subsystem stores
`data on at least one storage device, said storage device
`a series of blocks. The file management
`including
`system
`comprises an operating system-independent
`file map, a file
`command receiver module, and a file manage-
`management
`ment command execution module. The operating
`system-
`for each
`file map stores information
`independent
`identifying,
`file, block information
`identifying blocks on which the file
`receiver module
`is stored. The file management
`command
`receives a file management
`command. The file management
`command execution module executes the file management
`in relation
`command
`system-independent
`to the operating
`file map.
`
`20 Claims, 16 Drawing Sheets
`
`185. FILE MAP UTILIZATION MODULE 43 ESTABLISHES A
`DATA WRITTEN COUNTER AND A REMAINING DATA
`COUNTER AND INITIALIZE THEM TO ZERO AND THE
`IN THE FILE WRITE
`COUNT VALUE CONTAINED
`COMMAND, RESPECTIVELY
`
`186. FILE MAP UTILIZATION MODULE 43 GENERATES A
`VALUE IDENTIFYING THE AMOUNT OF DATA THAT WILL
`BE RETRIEVED FROM THE DISK EXTENT POINTED TO BY
`THE EXTENT DESCRIPTOR 54(f) THAT IS, IN TURN,
`POINTED TO BY THE CURRENT EXTENT POINTER
`
`7. FILE MAP UTILIZATION MODULE 43 RETRIEVES AN
`AMOUNT OF DATA CORRESPONDING TO THE VALUE
`GENERATED IN STEP 186 FROM BUFFER POINTED TO BY
`THE BUFFER POINTER IN THE FILE WRITE COMMAND
`FOR TRANSFER TO MASS STORAGE SUBSYSTEM 12, AND
`ENABLES THE MASS STORAGE SUBSYSTEM 12 TO
`STORE DATA ON THE DISK EXTENT POINTED TO BY THE
`EXTENT DESCRIPTOR 54(El THAT IS, IN TURN, POINTED
`TO BY THE CURRENT EXTENT POINTER, BEGINNING AT
`AN OFFSET POINTED TO BY THE CURRENT EXTENT
`FFSET POINTER
`
`188. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE DATA WRITTEN COUNTER AND DECREMENT THE
`REMAINING DATA COUNTER BY A VALUE
`CORRESPONDING TO THE AMOUNT OF DATA THAT HAS
`BEEN RECEIVED AND BUFFERED IN STEP 187
`
`BlackBerry Corporation Exhibit 1029, pg. 1
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 1 of 16
`
`/
`/
`/
`
`tf)
`CO
`
`(0
`
`CO
`
`UJ o )
`0
`
`UJ
`
`0
`u)
`
`CY
`
`0 0 I-
`o g
`& i~
`IXI +
`CI
`
`Oo' 2 I-
`I 5e
`Zo
`OK
`o
`
`I
`
`CL r)
`
`UJ P
`
`U
`
`0
`
`U
`
`o
`
`CL bl
`
`UJ Z 2 UJ
`U Q
`
`CL CC.
`
`' 0 LU
`o ~ c9
`Q UJ
`CQ CO
`
`I
`
`(a
`I~ +cv
`(0
`I &-
`i (8
`U 0
`
`0
`
`NMZ 0o5
`Z 4-I Mo
`
`I
`
`I
`
`) N
`064 I
`(3 +~
`0~
`
`I
`
`I
`
`BlackBerry Corporation Exhibit 1029, pg. 2
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 2 of 16
`
`6, 161, 111
`
`I— z
`
`UJ
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`Al
`CD
`
`Co
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I- z
`UJ I-
`X
`
`LLI
`
`CD
`
`I— z
`I-
`X
`
`I
`I
`
`I
`
`I
`
`I— z
`I ~ ~ X
`
`UJ
`
`UJ
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`n
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`lA
`I—
`
`LU
`
`X
`
`K~K
`
`R cL'
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`I
`I
`
`I
`
`I
`
`/
`
`/
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`/
`
`/
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`/
`I
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`/ /
`//
`//
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`
`I Z
`I Z
`I 0
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`F)
`
`Z
`Z
`0
`
`CA
`
`z
`0
`
`z
`Z 0
`
`C)
`
`UJ
`
`U
`
`z
`Z 0
`
`BlackBerry Corporation Exhibit 1029, pg. 3
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 3 of 16
`
`CV
`
`Z
`
`LA
`
`I
`
`I
`
`I g I
`I ~ I
`I 0 I
`I- — -I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`~
`
`~
`
`~
`
`'
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I ~
`I 0 I
`
`I
`
`I
`
`LU
`
`I
`
`I
`
`I x
`I- — — 4
`
`LU
`
`)
`
`~
`
`~
`
`~
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I ~
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`I
`I
`
`I Z
`
`LU
`
`)
`
`ol
`
`LA )
`
`CL I—
`Z'.
`LU
`)
`CL I
`
`UJ
`
`)
`
`C)
`
`CL
`
`LU
`
`U
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`) C4
`I g
`
`I
`
`I
`
`I
`
`I
`I Uj
`I Cl
`I- — -I
`
`I
`
`I
`
`I ~ I
`I — I
`I ~ I
`
`LU
`
`I
`)
`
`I
`
`I
`
`I
`
`I
`
`I
`
`0
`
`Z'.
`
`LU
`GO
`
`0
`
`CL
`
`I
`
`I ~
`I a
`
`lQ
`
`I
`
`I
`
`cO
`
`I 0 I Z
`I — I
`
`I
`
`I
`
`CO
`
`o
`
`I
`
`(8
`I-
`
`M
`
`C)
`LA
`
`I—
`Z'.
`LU
`CL
`
`LU
`
`U
`
`BlackBerry Corporation Exhibit 1029, pg. 4
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 4 of 16
`
`6, 161, 111
`
`100. FILE MAP GENERATOR 42 RECEIVES, FROM THE
`CONTROL MODULE 41, THE FILE NAME FOR A FILE
`MAINTAINED BY THE HOST COMPUTER 11 ON THE MASS
`STORAGE SUBSYSTEM 12 FOR WHICH A FILE MAP ENTRY
`50(f) IS TO BE GENERATED
`
`101. FILE MAP GENERATOR 42 QUERIES HOST
`COMPUTER'S FILE SYSTEM MANAGER PORTION 32 TO
`IDENTIFY THE PARTICULAR LOGICAL VOLUME IN WHICH
`THE FILE IDENTIFIED BY THE FILE NAME IS STORED
`
`102. HOST COMPUTER'S FILE SYSTEM MANAGER
`PORTION 32 IDENTIFIES THE LOGICAL VOLUME IN WHICH
`THE FILE IDENTIFIED BY THE FILE NAME IS STORED
`
`03. FILE MAP GENERATOR 42 QUERIES HOST
`COMPUTER'S LOGICAL VOLUME MANAGER PORTION 22
`TO IDENTIFY THE SERIES OF DISK EXTENTS, EACH
`INCLUDING THE IDENTIFICATION OF THE DISK STORAGE
`DEVICE 16(s) ON WHICH THE RESPECTIVE DISK EXTENTS
`IS STORED, ON WHICH DATA COMPRISING THE FILE IS
`STORED
`
`104. HOST COMPUTER'S LOGICAL VOLUME MANAGER
`PORTION 22 PROVIDES THE IDENTIFICATIONS OF THE
`SERIES OF DISK EXTENTS ON WHICH THE DATA
`COMPRISING THE FILE IS STORED
`
`FI 2
`
`BlackBerry Corporation Exhibit 1029, pg. 5
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 5 of 16
`
`6, 161, 111
`
`105. FILE MAP GENERATOR 42 GENERATES A FILE MAP
`ENTRY 50(f) INCLUDING FILE NAME IN FILE 50, DISK
`IN DISK STORAGE
`STORAGE DEVICE IDENTIFICATIONS
`IN DISK
`DEVICE LIST 52 AND DISK EXTENT INFORMATION
`EXTENT LIST 54
`
`106. FILE MAP GENERATOR 42 NOTIFIES THE CONTROL
`MODULE 41 THAT IT HAS COMPLETED THE PROCESSING
`OPERATIONS FOR THE FILE IDENTIFIED IN STEP 100
`
`YES
`
`107. CONTROL MODULE 41 DETERMINES WHETHER
`THERE IS AN ADDITIONAL FILE FOR WHICH A FILE MAP
`ENTRY 50(f) IS TO BE GENERATED
`
`108. CONTROL MODULE 41 ENABLES THE FILE MAP
`GENERATOR 42 TO SAVE THE FILE MAP 40 FOR USE
`DURING THE SUBSEQUENT OPERATIONS TO BE
`PERFORMED DURING A BACKUP OR RESTORE
`OPERATION
`
`2A
`
`BlackBerry Corporation Exhibit 1029, pg. 6
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 6 of 16
`
`6, 161, 111
`
`120. FILE MAP UTILIZATION MODULE 43 RECEIVES FILE
`INCLUDING THE FILE NAME OF THE
`OPEN COMMAND
`FILE TO BE OPENED, AND POSSIBLY ALSO A FILE MAP
`POINTER POINTING TO A FILE MAP 40 THAT INCLUDES A
`FILE MAP ENTRY 50(f) FOR THE FILE
`
`YES
`
`121. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE FILE OPEN COMMAND INCLUDES A FILE
`MAP POINTER
`
`122. FILE MAP UTILIZATION MODULE 43 TRANSFER THE
`FILE OPEN COMMAND TO THE BACKUP SERVER'S FILE
`SYSTEM MANAGER FOR PROCESSING IN A
`CONVENTIONAL MANNER
`
`23. FILE MAP UTILIZATION MODULE 43 RETRIEVES THE
`FILE MAP ENTRY 50(f) THAT IS ASSOCIATED WITH THE
`FILE IDENTIFIED BY THE FILE NAME IN THE FILE OPEN
`COMMAND, FROM THE MAP FILE POINTED TO BY THE
`FILE MAP POINTER PROVIDED IN THE FILE OPEN
`COMMAND, AND STORES IT IN THE BACKUP SERVER'S
`MEMORY
`
`124. FILE MAP UTILIZATION MODULE 43 ESTABLISHES
`AND INITIALIZES A CURRENT EXTENT POINTER, A
`CURRENT EXTENT OFFSET POINTER, AND A FILE OFFSET
`POINTER
`
`125. FILE MAP UTILIZATION MODULE 43 PROVIDES THE
`CONTROL MODULE 41 WITH A FILE DESCRIPTOR FOR
`THE FILE
`
`FI
`
`BlackBerry Corporation Exhibit 1029, pg. 7
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 7 of 16
`
`6, 161, 111
`
`140. FILE MAP UTILIZATION MODULE 43 RECEIVES THE
`FILE SEEK COMMAND
`
`YES
`
`141. FILE MAP UTILIZATION MODULE DETERMINES
`WHETHER THE FILE SEEK COMMAND INCLUDES A FILE
`DESCRIPTOR THAT IDENTIFIES A FILE FOR WHICH A FILE
`MAP ENTRY 50(F) WAS LOADED INTO THE BACKUP
`SERVER'S MEMORY IN STEP 123
`
`142. FILE MAP UTILIZATION MODULE 43 TRANSFERS THE
`FILE SEEK COMMAND TO THE BACKUP SERVER'S FILE
`SYSTEM MANAGER FOR PROCESSING IN A
`CONVENTIONAL MANNER
`
`143. FILE MAP UTILIZATION MODULE 43 GENERATES A
`FILE OFFSET POINTER UPDATE VALUE IN THE MANNER
`SPECIFIED IN THE POSITION IN FILE ADJUSTMENT FLAG,
`USING THE POSITION IN FILE VALUE PROVIDED IN THE
`FILE SEEK COMMAND
`
`NO
`
`144. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE FILE OFFSET POINTER UPDATE VALUE IS
`GREATER THAN THE CURRENT FILE OFFSET POINTER
`
`Y S
`
`145. FILE MAP UTILIZATION MODULE INITIALIZES BASIS
`VALUE AS THE CURRENT FILE MAP POINTER AND
`EXTENT POINTER AS THE CURRENT EXTENT POINTER
`
`FI
`
`BlackBerry Corporation Exhibit 1029, pg. 8
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 8 of 16
`
`146. FILE MAP UTILIZATION MODULE 43 INITIALIZES THE
`BASIS VALUE AS ZERO AND THE EXTENT POINTER TO
`POINT TO THE FIRST EXTENT DESCRIPTOR 54(E) IN THE
`DESCRIPTOR LIST 54 OF THE FILE'S FILE MAP ENTRY
`50(F) IN FILE MAP 40
`
`147. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE FILE OFFSET POINTER UPDATE VALUE
`IN THE EXTENT IDENTIFIED BY
`POINTS TO A LOCATION
`THE EXTENT POINTER
`
`148. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE BASIS VALUE AND THE EXTENT POINTER
`
`YES
`
`149. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE EXTENT POINTER POINTS TO AN EXTENT
`DESCRIPTOR 54(E) IN THE EXTENT DESCRIPTOR LIST 54
`
`F
`
`A
`
`BlackBerry Corporation Exhibit 1029, pg. 9
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 9 of 16
`
`6, 161, 111
`
`150. FILE MAP UTILIZATION MODULE 43 UPDATES THE
`CURRENT EXTENT POINTER TO POINT TO THE EXTENT
`IDENTIFIED BY THE EXTENT POINTER
`
`151. FILE MAP UTILIZATION MODULE 43 GENERATES A
`CURRENT EXTENT OFFSET POINTER AS THE
`DIFFERENCE BETWEEN THE FILE OFFSET POINTER
`UPDATE VALUE AND THE BASIS VALUE
`
`152. FILE MAP UTILIZATION MODULE 43 LOADS THE
`ERROR VALUE INTO THE CURRENT EXTENT POINTER
`AND CURRENT EXTENT OFFSET POINTER.
`
`FI
`
`BlackBerry Corporation Exhibit 1029, pg. 10
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 10 of 16
`
`6, 161, 111
`
`160. FILE MAP UTILIZATION MODULE 43 RECEIVES THE
`FILE READ COMMAND FROM THE CONTROL MODULE 41
`
`YES
`
`161. FILE MAP UTILIZATION ELEMENT 43 DETERMINES
`IN THE
`WHETHER THE FILE DESCRIPTOR CONTAINED
`FILE READ COMMAND IS ASSOCIATED WITH A FILE FOR
`WHICH A FILE MAP ENTRY 50(f) WAS LOADED INTO THE
`BACKUP SERVER'S MEMORY DURING EXECUTION OF
`THE FILE OPEN COMMAND
`
`NO
`
`162. FILE MAP UTILIZATION MODULE 43 TRANSFERS THE
`FILE READ COMMAND TO THE BACKUP SERVER'S FILE
`SYSTEM MANAGER FOR PROCESSING IN A
`CONVENTIONAL MANNER
`
`NO
`
`163. FILE MAP UTILIZATION MODULE 43 EXAMINES THE
`CURRENT EXTENT POINTER TO DETERMINE IF IT
`CONTAINS THE ERROR VALUE
`
`Y S
`
`164. FILE MAP UTILIZATION MODULE 43 NOTIFIES THE
`CONTROL MODULE 41
`
`FI
`
`BlackBerry Corporation Exhibit 1029, pg. 11
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 11 of 16
`
`165. FILE MAP UTILIZATION MODULE 43 ESTABLISHES A
`DATA READ COUNTER AND A REMAINING DATA
`COUNTER AND INITIALIZE THEM TO ZERO AND THE
`IN THE FILE READ COMMAND,
`COUNT VALUE CONTAINED
`RESPECTIVELY
`
`166. FILE MAP UTILIZATION MODULE 43 GENERATES A
`VALUE IDENTIFYING THE AMOUNT OF DATA THAT WILL
`BE RETRIEVED FROM THE DISK EXTENT POINTED TO BY
`THE EXTENT DESCRIPTOR 54(f) THAT IS, IN TURN,
`POINTED TO BY THE CURRENT EXTENT POINTER
`
`67. FILE MAP UTILIZATION MODULE 43 ENABLES THE
`MASS STORAGE SUBSYSTEM 12 TO RETRIEVE AN
`AMOUNT OF DATA CORRESPONDING TO THE VALUE
`GENERATED IN STEP 166, FROM THE DISK EXTENT
`POINTED TO BY THE EXTENT DESCRIPTOR 54(E) THAT IS,
`IN TURN, POINTED TO BY THE CURRENT EXTENT
`POINTER, BEGINNING AT AN OFFSET POINTED TO BY
`THE CURRENT EXTENT OFFSET POINTER; FILE MAP
`UTILIZATION MODULE 43 STORES THE DATA IN THE
`BUFFER POINTED TO BY THE BUFFER POINTER
`ROVIDED IN THE FILE READ COMMAND
`
`168. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE DATA READ COUNTER AND DECREMENT THE
`REMAINING DATA COUNTER BY A VALUE
`CORRESPONDING TO THE AMOUNT OF DATA THAT HAS
`BEEN RECEIVED AND BUFFERED IN STEP 167
`
`BlackBerry Corporation Exhibit 1029, pg. 12
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 12 of 16
`
`FI B
`
`169. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`BOTH THE FILE OFFSET POINTER AND THE CURRENT
`EXTENT OFFSET POINTER BY A VALUE CORRESPONDING
`TO THE AMOUNT OF DATA THAT HAS BEEN RECEIVED
`AND BUFFERED
`
`NO
`
`170. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER ALL OF THE DATA TO BE RETRIEVED IN
`CONNECTION WITH EXECUTION OF THE FILE READ
`COMMAND HAS BEEN RETRIEVED AND BUFFERED
`
`Y S
`
`171. FILE MAP UTILIZATION MODULE 43 RETURNS THE
`VALUE PROVIDED BY THE DATA READ COUNTER TO THE
`CONTROL MODULE 41
`
`172. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE CURRENT EXTENT POINTER AND SETS THE
`CURRENT EXTENT OFFSET POINTER TO ZERO
`
`173. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE CURRENT EXTENT POINTER POINTS TO
`AN EXTENT DESCRIPTOR 54(E) IN THE EXTENT
`DESCRIPTOR LIST 54 OF THE FILE MAP ENTRY 50(0
`ASSOCIATED WITH THE FILE FROM WHICH DATA IS
`BEING RETRIEVED
`
`NO
`
`YES
`
`BlackBerry Corporation Exhibit 1029, pg. 13
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 13 of 16
`
`6, 161, 111
`
`180. FILE MAP UTILIZATION MODULE 43 RECEIVES THE
`FILE WRITE COMMAND FROM THE CONTROL MODULE 41
`
`YES
`
`181. FILE MAP UTILIZATION ELEMENT 43 DETERMINES
`IN THE
`WHETHER THE FILE DESCRIPTOR CONTAINED
`FILE WRITE COMMAND IS ASSOCIATED WITH A FILE FOR
`WHICH A FILE MAP ENTRY 50(f) WAS LOADED INTO THE
`BACKUP SERVER'S MEMORY DURING EXECUTION OF
`THE FILE OPEN COMMAND
`
`NO
`
`182. FILE MAP UTILIZATION MODULE 43 TRANSFERS THE
`FILE WRITE COMMAND TO THE BACKUP SERVER'S FILE
`SYSTEM MANAGER FOR PROCESSING IN A
`CONVENTIONAL MANNER
`
`NO
`
`183. FILE MAP UTILIZATION MODULE 43 EXAMINES THE
`CURRENT EXTENT POINTER TO DETERMINE IF IT
`CONTAINS THE ERROR VALUE
`
`Y S
`
`184. FILE MAP UTILIZATION MODULE 43 NOTIFIES THE
`CONTROL MODULE 41
`
`BlackBerry Corporation Exhibit 1029, pg. 14
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 14 of 16
`
`6, 161, 111
`
`185. FILE MAP UTILIZATION MODULE 43 ESTABLISHES A
`DATA WRITTEN COUNTER AND A REMAINING DATA
`COUNTER AND INITIALIZE THEM TO ZERO AND THE
`IN THE FILE WRITE
`COUNT VALUE CONTAINED
`COMMAND, RESPECTIVELY
`
`186. FILE MAP UTILIZATION MODULE 43 GENERATES A
`VALUE IDENTIFYING THE AMOUNT OF DATA THAT WILL
`BE RETRIEVED FROM THE DISK EXTENT POINTED TO BY
`THE EXTENT DESCRIPTOR 54(f) THAT IS, IN TURN,
`POINTED TO BY THE CURRENT EXTENT POINTER
`
`7. FILE MAP UTILIZATION MODULE 43 RETRIEVES AN
`AMOUNT OF DATA CORRESPONDING TO THE VALUE
`GENERATED IN STEP 186 FROM BUFFER POINTED TO BY
`THE BUFFER POINTER IN THE FILE WRITE COMMAND
`FOR TRANSFER TO MASS STORAGE SUBSYSTEM 12, AND
`ENABLES THE MASS STORAGE SUBSYSTEM 12 TO
`STORE DATA ON THE DISK EXTENT POINTED TO BY THE
`EXTENT DESCRIPTOR 54(E) THAT IS, IN TURN, POINTED
`TO BY THE CURRENT EXTENT POINTER, BEGINNING AT
`AN OFFSET POINTED TO BY THE CURRENT EXTENT
`FFSET POINTER
`
`188. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE DATA WRITTEN COUNTER AND DECREMENT THE
`REMAINING DATA COUNTER BY A VALUE
`CORRESPONDING TO THE AMOUNT OF DATA THAT HAS
`BEEN RECEIVED AND BUFFERED IN STEP 187
`
`BlackBerry Corporation Exhibit 1029, pg. 15
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 15 of 16
`
`89. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`BOTH THE FILE OFFSET POINTER AND THE CURRENT
`EXTENT OFFSET POINTER BY A VALUE CORRESPONDING
`TO THE AMOUNT OF DATA THAT HAS BEEN
`TRANSFERRED TO MASS STORAGE SUBSYSTEM FOR
`STORAGE
`
`NO
`
`190. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER ALL OF THE DATA TO BE WRITTEN IN
`CONNECTION WITH EXECUTION OF THE FILE WRITE
`COMMAND HAS BEEN WRITTEN
`
`Y S
`
`191. FILE MAP UTILIZATION MODULE 43 RETURNS THE
`VALUE PROVIDED BY THE DATA WRITTEN COUNTER TO
`THE CONTROL MODULE 41
`
`192. FILE MAP UTILIZATION MODULE 43 INCREMENTS
`THE CURRENT EXTENT POINTER AND SETS THE
`CURRENT EXTENT OFFSET POINTER TO ZERO
`
`193. FILE MAP UTILIZATION MODULE 43 DETERMINES
`WHETHER THE CURRENT EXTENT POINTER POINTS TO
`AN EXTENT DESCRIPTOR 54(E) IN THE EXTENT
`DESCRIPTOR LIST 54 OF THE FILE MAP ENTRY 50(f)
`ASSOCIATED WITH THE FILE FROM WHICH DATA IS
`BEING RETRIEVED
`
`NO
`
`YES
`
`BlackBerry Corporation Exhibit 1029, pg. 16
`
`

`

`U. S. Patent
`
`Dec. 12, 2000
`
`Sheet 16 of 16
`
`6, 161, 111
`
`200. FILE MAP UTILIZATION MODULE 43 RECEIVES THE
`FILE CLOSE COMMAND FROM THE CONTROL MODULE 41
`
`YES
`
`01. FILE MAP UTILIZATION ELEMENT 43 DETERMINES
`IN THE
`WHETHER THE FILE DESCRIPTOR CONTAINED
`FILE READ COMMAND IS ASSOCIATED WITH A FILE FOR
`WHICH A FILE MAP ENTRY 50(f) WAS LOADED INTO THE
`BACKUP SERVER'S MEMORY DURING EXECUTION OF
`THE FILE OPEN COMMAND
`
`202. FILE MAP UTILIZATION MODULE 43 TRANSFERS THE
`FILE CLOSE COMMAND TO THE BACKUP SERVER'S FILE
`SYSTEM MANAGER FOR PROCESSING IN A
`CONVENTIONAL MANNER
`
`203. FILE MAP UTILIZATION MODULE 43 PROCEEDS TO
`REMOVE THE FILE MAP ENTRY 50(f) FROM THE BACKUP
`SERVER'S MEMORY.
`
`BlackBerry Corporation Exhibit 1029, pg. 17
`
`

`

`SYSTEM AND METHOD FOR PERFORMING
`FILE-HANDLING OPERATIONS IN A
`DIGITAL DATA PROCESSING SYSTEM
`USING AN OPERATING
`SYSTEM-INDEPENDENT FILE MAP
`
`U. S. patent application Ser. No. 09/052, 579, filed on
`in the names of Madhav Mutalik, et al. ,
`even date herewith
`and entitled "System And Method For Backing Up Data
`Stored In Mass Storage Subsystem Under Control Of A
`Backup Server", assigned to the assignee of this application
`and incorporated herein by reference.
`U. S. patent application Ser. No. 09/052, 318, filed on
`in the names of Madhav Mutalik, et al. ,
`even date herewith
`and entitled "System And Method For Backing Up Data
`Stored In Multiple Mirrors On A Mass Storage Subsystem
`Under Control Of A Backup Server", assigned
`to
`the
`assignee of this application
`incorporated
`herein by
`and
`reference.
`U. S. patent application Ser. No. 09/052, 209, filed on
`in the names of Madhav Mutalik, et al. ,
`even date herewith
`and entitled "System And Method For Generating An Oper-
`File Map", assigned
`ating System-Independent
`to
`the
`assignee of this application
`incorporated
`herein by
`and
`reference.
`
`FIELD OF THE INVENTION
`
`to the field of digital data
`relates generally
`The invention
`to mass digital
`processing
`systems and more particularly
`data storage subsystems. The invention provides a system
`and method for performing backup of data stored in a mass
`storage subsystem.
`
`BACKGROUND OF THE INVENTION
`
`Digital computer systems are used in a number of appli-
`cations in which virtually continuous availability of data is
`to the operation of businesses or other entities
`important
`using the systems. Generally, computer centers will periodi-
`cally produce back-up copies of data on their various digital
`systems. Such back-up copies are usually not
`computer
`maintained on a continuous basis, but instead at particular
`in time, often at night when
`the normal processing
`points
`load on the computer centers is reduced and modifications
`to
`the data being backed up may be minimized, and in any case
`the data at the particular points in time at which the
`represent
`if a failure
`back-up copies are generated. Accordingly,
`occurs between back-ups, data which has been received and
`processed by the digital computer
`systems since the last
`back-up copy was produced, may be lost. Typically, such
`back-up copies will be maintained by the computer centers
`at their respective sites so that they may be used in the event
`of a failure, although some olf-site archival back-ups may be
`maintained. Significant additional problems arise in the case
`of, for example, catastrophic events that can occur, such as
`fire, flood or other natural
`may result from, for example,
`tampering or sabotage and
`disasters,
`the like,
`intentional
`to
`or intentional damage
`which may result in unintentional
`an entire site or some significant portion thereof, since some
`or all of the back-up copies may also be damaged and the
`thereon may be unavailable.
`data contained
`Several backup strategies have been developed.
`In one
`and controls the data to
`strategy, software which maintains
`be backed up, such as database
`software,
`initiates
`and
`performs the backup operation. In such an arrangement data,
`in the form of incremental changes to a database,
`generally
`is provided by the database software
`to a backup manage-
`
`ment software, which stores the data on a backup device.
`One advantage of this strategy is that, since only incremental
`changes are backed up, less data needs to be backed up at
`any point in time. A disadvantage
`is, however,
`that although
`less data is copied with this strategy, a load is still exerted
`the database software.
`on the production system processing
`In a second strategy, backups are performed outside
`the
`database software. In this strategy, data files are backed up
`of the database software. While
`this mini-
`independently
`mizes
`the load on the production
`system processing
`the
`database software and can result
`in relatively high-speed
`backups of full data files, the backup and restore operations
`do not make use of the facilities that are currently provided
`in commercial database software.
`U. S. patent application Ser. No. 09/052, 579 filed on even
`in the names of Madhav Mutalik, et al. , and
`date herewith
`entitled "System And Method For Backing Up Data Stored
`In Mass Storage Subsystem Under Control Of A Backup
`Server" and U. S. patent application Ser. No. 09/052, 318,
`in the names of Madhav Mutalik,
`filed on even date herewith
`et al. , and entitled "System And Method For Backing Up
`Data Stored In Multiple Mirrors On A Mass Storage Sub-
`system Under Control Of A Backup Server" (both of which
`et al. ,
`the Mutalik,
`identified
`as
`herein
`are generally
`for backing up data
`describe arrangements
`applications)
`stored on a mass storage subsystem using a backup server.
`to requests from an application executed by, for
`In response
`the backup server performs
`example, a host computer,
`the
`the host computer of that
`relieving
`backup operation,
`the host computer
`to perform
`responsibility
`and allowing
`other operations concurrently with
`the backup operation,
`the throughput of the host computer.
`thereby enhancing
`In
`is in the form of a
`the backup server
`one embodiment,
`the computer comprising,
`computer,
`suitably programmed
`for example, a workstation or personal computer. Aproblem
`since the file
`arises in connection with such an arrangement,
`system and file formats and structures provided by the host
`computer's operating
`to manage data files for the
`system
`host computer and its applications, may dilfer from those
`server's
`system used by
`that
`the backup
`the operating
`computer.
`
`SUMMARY OF THE INVENTION
`
`The invention provides anew and improved
`system and
`for **backing up data stored on a mass storage
`method
`subsystem under control of a backup server.
`In brief summary, a file management
`system manages files
`to file
`stored on a mass storage
`subsystem
`in response
`management commands. The mass storage subsystem stores
`data on at least one storage device, said storage device
`a series of blocks. The file management
`including
`system
`comprises an operating system-independent
`file map, a file
`command receiver module, and a file manage-
`management
`ment command execution module. The operating
`system-
`for each
`file map stores information
`independent
`identifying,
`file, block information
`identifying blocks on which the file
`receiver module
`is stored. The file management
`command
`receives a file management
`command. The file management
`command execution module executes the file management
`in relation
`command
`system-independent
`to the operating
`file map.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`65
`
`is pointed out with particularity
`This invention
`in the
`appended claims. The above and further advantages of this
`invention may be better understood
`by referring
`to the
`
`BlackBerry Corporation Exhibit 1029, pg. 18
`
`

`

`taken in conjunction with the accom-
`following description
`in which:
`panying drawings,
`FIG. 1 is a functional block diagram of a digital data
`for backing up
`processing system including an arrangement
`in accordance with the invention;
`data, constructed
`FIGS. 1A through 1C are detailed diagrams useful
`in
`the operation of the digital data processing
`understanding
`in FIG. 1; and
`system depicted
`FIGS. 2 through 7 are flowcharts depicting operations
`performed by the digital data processing
`system during a
`backup and restoration operation, useful
`in understanding
`the invention.
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`FIG. 1 is a functional block diagram of a digital data
`processing system 10 including an arrangement
`for backing
`in accordance with the invention. With
`up data, constructed
`system 10
`to FIG. 1, digital data processing
`reference
`includes host computer 11, one or more mass storage sub-
`identified by reference numeral 12, a
`systems generally
`server 13, and one or more backup data stores
`backup
`identified by reference numeral 14. The host
`generally
`computer 11, which, as will be described below, also oper-
`ates as a backup client, executes one or more applications,
`identified by reference numeral 17, which make
`generally
`use of the data stored
`in the mass storage subsystems 12,
`execution occurring under control of an operating
`system
`18. In one particular
`embodiment, one applica-
`illustrative
`tion executed by the host computer 11 comprises
`the well-
`known Oracle 7 database management
`(DBMS)
`system
`it will
`program available from Oracle Corporation, although
`that the digital computer system may also or
`be appreciated
`instead process DBMS programs from other manufacturers,
`as well as other programs which are not DBMS programs.
`In the embodiment described herein, it will be assumed
`that
`the system 10 includes one mass storage subsystem 12
`that embodiments of the
`it will be appreciated
`although
`invention may include multiple mass storage subsystems of
`and architectures.
`varying configurations
`subsystem 12 used
`The mass storage
`in digital data
`processing system 10 includes a mass- or secondary-storage
`subsystem which stores data in disk-based storage. In one
`the mass storage subsystem 12 comprise
`embodiment,
`the
`in, for
`to that described
`mass storage subsystem
`similar
`example, U. S. Pat. No. 5, 206, 939, entitled "System And
`Method For Disk Mapping And Data Retrieval, " issued Apr.
`27, 1993 to Moshe Yanai, et al, U. S. patent application. Ser.
`No. 07/893, 509 filed Jun. 4, 1995, in the name of Moshe
`Yanai, et al. , entitled "System And Method For Dynamically
`Controlling Cache Management, " and U. S. Pat. No. 5, 592,
`"Cache Management
`432, entitled
`System Using Time
`Stamping For Replacement Queue, " issued Jan. 7, 1997 in
`the name of Natan Vishlitzky, et al. , all of which are assigned
`to the assignee of the present
`and incorporated
`invention
`it will be appreciated
`herein by reference, although
`that any
`subsystem may be used with
`mass storage
`the present
`In that embodiment,
`the mass storage subsystem
`invention.
`12 includes one or more disk storage units which store data
`large caches to cache
`in magnetic form, and further utilizes
`data retrieved from the disk storage units to be transferred
`to
`the host 11 for processing and updated data provided by the
`host 11 to be transferred
`to the disk storage units for storage,
`all under control of circuitry generally
`identified as control
`circuitry 15. In that embodiment,
`the mass storage sub-
`system 12 stores data in multiple disk storage devices 16(1)
`through 16(S) (generally
`identified by reference numeral
`16(s)).
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The backup server 13 and backup data stores 14 operate
`to back up the data stored on the mass storage subsystem 12,
`the likelihood of data loss in the event of
`thereby reducing
`a malfunction or other failure of one or more disk drive units
`or other components of the mass storage subsystem 12. The
`operations performed by the backup server 13 and backup
`data stores 14 in performing backup operations
`in respective
`embodiments of system 10 are described
`in detail
`in the
`and will not be
`aforementioned Mutalik, et al, applications
`the backup server 13
`in detail. Generally,
`described herein
`initiates backup operations
`therefor
`to requests
`in response
`from the host computer 11, so that the host computer 11 is
`elfectively a backup client of the backup server 13. In one
`server 13 includes
`embodiment,
`a suitably-
`the backup
`or
`such as a workstation
`digital computer,
`programmed
`personal computer. After receiving a request from the host
`computer 11, the backup server 13 will initiate a backup
`in connection with data stored on the mass storage
`operation
`subsystem 12. During a backup operation,
`the backup server
`13 will retrieve data that is to be backed up from the mass
`storage subsystem 12 and transfer it to the backup data store
`14 for backup storage. In one embodiment,
`the backup data
`store 14 stores data provided thereto by the backup server 13
`tape cartridges (not separately shown), and the
`on magnetic
`backup data store 14 will include one or more drives and
`associated circuitry (also not separately shown) for storing
`the data on the cartridges. The backup data store 14 may also
`for loading respective
`include an autochanger
`arrangement
`the drives, and for removing
`respective
`cartridges onto
`cartridges
`from the drives after they are full.
`In addition
`to performing backup operations,
`the backup
`server 13 and backup data store 14 can also perform a restore
`in which data which has been backed up onto the
`operation,
`backup data store 14, is restored
`to the mass storage sub-
`system 12. This may occur, for example, following correc-
`tion of a malfunction
`in the mass storage subsystem 12 or the
`host computer 11 in which data may have become lost or
`corrupted. The operations performed by the backup server
`13 and backup data stores 14 in performing
`restore opera-
`tions in respective embodiments of system 10 are described
`in detail in the aforementioned Mutalik, et al, applications
`and will also not be described herein
`in detail. In a restore
`the backup server 13, after receiving a request
`operation,
`ther