United States Patent [19J
`Hitz et al.
`
`[54] METHOD FOR MAINTAINING CONSISTENT
`STATES OF A FILE SYSTEM AND FOR
`CREATING USER-ACCESSIBLE READ-ONLY
`COPIES OF A FILE SYSTEM
`
`[75]
`
`Inventors: David Hitz, Sunnyvale; Michael
`Malcolm, Los Altos; James Lau,
`Cupertino; Byron Rakitzis, Mountain
`View, all of Calif.
`
`[73] Assignee: NetworkAppliance, Inc., Santa Clara,
`Calif.
`
`[21]
`
`Appl. No.: 454,921
`
`[22]
`
`Filed:
`
`May 31, 1995
`
`[63]
`
`[51]
`[52]
`[58]
`
`[56]
`
`Related U.S. Application Data
`
`Continuation of Ser. No. 71,643, Jun. 3, 1993, abandoned.
`Int. Cl. 6
`...................................................... G06F 17/30
`U.S. Cl. ............................................. 707/203; 707/205
`Field of Search ...................................... 395/621, 619
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,075,691
`4,156,907
`4,333,144
`4,377,843
`4,399,503
`4,456,957
`4,459,664
`4,488,231
`4,527,232
`4,550,368
`4,685,125
`4,710,868
`4,719,569
`4,742,447
`4,761,785
`4,766,534
`4,780,821
`
`... ... ... ... ... .... ... ... ... 395/884
`2/1978 Davis et a!.
`5/1979 Rawlings et a!. .................. 395/200.01
`6/1982 Whiteside et a!. ...................... 395/672
`3/1983 Garringer et a!.
`...................... 395/890
`8/1983 Hawley ................................... 395/440
`6/1984 Schieltz ................................... 395/824
`7/1984 Pottier eta!. ........................... 395/675
`12/1984 Yu eta!. ................................. 395/868
`7/1985 Bechtolsheim .......................... 395/416
`10/1985 Bechtolsheim .......................... 395/416
`8/1987 Zave ... ... ... ... ... .... ... ... ... ... ... .... ... . 379/96
`12/1987 Cocke et a!. ............................ 395/311
`1!1988 Ludemann eta!. ..................... 395/729
`5/1988 Duvall eta!. ........................... 364/200
`8/1988 Clark et a!. .... ... ... ... ... .... ... ... ... .. 371/51
`8/1988 DeBenedictis ..................... 395/200.14
`10/1988 Crossley .................................. 395/670
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005819292A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,819,292
`Oct. 6, 1998
`
`OTHER PUBLICATIONS
`
`Bach, "The Design of the UNIX Operating System", Pren(cid:173)
`tice-Hall, 1986, pp. 38-90 and 325-329, Jan. 1986.
`Beach, Richard J., et al., "The Message is The Medium:
`Multiprocess Structuring of an Interactive Paint Program",
`Computer Graphics, vol. 16, No. 3, Jul. 1982, pp. 277-287.
`Britton, Dianne E. et al., "A Interprocess Communication
`Facility for Distributed Applications", RCA Laboratories,
`David Sarnoff Research Center. Princeton, N.J., Copyright
`1980 IEEE, Jan. 1980.
`Carr, Robert et al., The Power of PenPoint, Ch 5, the Class
`Manager, Copyright 1991, Addison-Wesley, Jan. 1991.
`Cashin, "Interprocess Communication", Bell-Northern
`Research, Document No. 8005014, Jan. 1980.
`
`(List continued on next page.)
`
`Primary Examiner-Paul R. Lintz
`Attorney, Agent, or Firm--D' Alessandro & Ritchie
`
`[57]
`
`ABSTRACT
`
`A method is disclosed for maintaining consistent states of a
`file system. The file system progresses from one self(cid:173)
`consistent state to another self-consistent state. The set of
`self-consistent blocks on disk that is rooted by a root inode
`is referred to as a consistency point. The root inode is stored
`in a file system information structure. To implement con(cid:173)
`sistency points, new data is written to unallocated blocks on
`disk. A new consistency point occurs when the file system
`information structure is updated by writing a new root inode
`into it. Thus, as long as the root inode is not updated, the
`state of the file system represented on disk does not change.
`The method also creates snapshots that are user-accessible
`read-only copies of the file system. A snapshot uses no disk
`space when it is initially created. It is designed so that many
`different snapshots can be created for the same file system.
`Unlike prior art file systems that create a done by duplicating
`an entire inode file and all indirect blocks, the method of the
`present invention duplicates only the inode that describes the
`inode file. A multi-bit free-block map file is used to prevent
`data referenced by snapshots from being overwritten on
`disk.
`
`(List continued on next page.)
`
`20 Claims, 39 Drawing Sheets
`
`CP-BIT
`
`SNAPSHOT BITS (BIT 1 - BIT 20)
`
`111 OA
`
`UPPER 11 BITS (BIT 21 -BIT 31)
`ARE RESERVED
`
`FS-BIT
`
`0
`
`0
`
`0
`
`0
`
`...
`
`0
`
`0
`
`FREE BLOCK
`
`1110A
`I_
`
`I
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`BLOCK IN
`ACTIVE FILE SYSTEM
`
`1110A
`BITO ~
`I 1
`I
`FS-BIT
`
`Microsoft Ex. 1017, p. 1
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`5,819,292
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,783,730 11/1988 Fischer .................................... 395/825
`4,803,621
`2/1989 Kelly ....................................... 395/405
`4,819,159
`4/1989 Shipley et a!. ..................... 395/182.17
`4,825,354
`4/1989 Agrawal et a!. ........................ 395/610
`4,875,159 10/1989 Cary et a!. .............................. 364/200
`4,887,204 12/1989 Johnson et a!. ......................... 395/610
`4,897,781
`1!1990 Chang eta!. ........................... 395/617
`4,914,583
`4/1990 Weisshaar eta!. ..................... 395/680
`5,043,871
`8/1991 Nishigaki et a!.
`...................... 395/600
`5,043,876
`8/1991 Terry ....................................... 395/600
`5,134,619
`7/1992 Henson eta!. ......................... 371/40.1
`5,155,835 10/1992 Belsan ..................................... 395/425
`5,163,131 11/1992 Row et a!. .............................. 395/200
`5,163,148 11/1992 Walls ...................................... 395/600
`5,195,100
`3/1993 Katz et a!. ................................ 371/66
`5,218,695
`6/1993 Noveck et a!.
`......................... 395/600
`5,218,696
`6/1993 Baird et a!. ............................. 395/600
`5,235,601
`8/1993 Stallmo et a!.
`........................ 371/40.1
`5,255,270 10/1993 Yanai et a!. ............................ 371/10.2
`5,274,799 12/1993 Brant eta!. ............................. 395!575
`5,274,807 12/1993 Hoshen et a!. .......................... 395!650
`5,276,840
`1!1994 Yu ........................................... 395/425
`5,276,867
`1!1994 Kenley et a!. .......................... 395/600
`5,305,326
`4/1994 Solomon et a!.
`...................... 371/11.1
`5,313,626
`5/1994 Jones et a!. ............................. 395!575
`5,315,602
`5/1994 Noya et a!. ............................ 371/40.4
`5,355,453 10/1994 Row et a!. .
`5,357,509 10/1994 Ohizumi ................................. 371/10.1
`1!1995 Lui eta!. ................................ 395!575
`5,379,417
`
`01HER PUBLICATIONS
`
`Chao, Chia et al., "MIME: A High Performance Storage
`Device With Strong Recovery Guarantees", Hewlett-Pack(cid:173)
`ard Co, Mar. 18, 1992.
`Charlton, David, The Thoth System: Multiprocess Structur(cid:173)
`ing and Portability, Ch2 Thoth Program Environment, and
`Ch 3: TRoth Kernel Design, (1982, North-Holland), Jan.
`1982.
`Cohen, Jacques, Garbage Collection of Linked Data Struc(cid:173)
`tures < Department of Physics, Brandeis University,
`Waltham, Ma, Computing Surveys, vol. 13, No. 3, Sep.
`1981.
`Deitel, An Introduction to Operating Structures, Addison(cid:173)
`Wesley, Jan. 1984, pp. 302-334.
`de Jonge, Wiebrand et al., The Logical Disk, A New
`Approach to Inmproving File Systems, Jan. 1984, p. 1-14,
`unpublished.
`English et al., Loge: A Self-Organizing Disk Controller,
`Software
`and
`Systems
`Laboratory,
`Jan.
`1991
`(Hewlett-Packard.
`Anonymous, File Systems, Chapter 5, pp. 251-273, Jan.
`1995.
`Mulqueen, John T., Product Analysis Review, Communica(cid:173)
`tions Week, vol. 452, pp. 25, May 3, 1993.
`Hitz et al., File System for an NFS File Server Appliance,
`Abstract only from INSPEC Abstravt # C9502-6120-020,
`Proceedings of the 1994 UNIX Winter Conference, 17-21
`Jan. 1994.
`Simpson, David, '"Appliances' Take Over File Server
`Role", Digital News and Review, vol. 11, No. 6, pp. 1-2,
`Mar. 21, 1994.
`Chutani et al, "The Episode File System", USENIX(cid:173)
`Winter 1992, pp. 43-60.
`
`Tan, et al., "SOS-Stan's Own Server: A NFS File Server
`for the IBM PC," Computer Science Research Department,
`Information and Computing Sciences Division, Lawrence
`Berkeley Laboratory, Aug. 17, 1988.
`Sandberg, "The Sun Network File System: Design, Imple(cid:173)
`mentation and Experience," Sun Microsystems, Inc. Tech(cid:173)
`nical Report, 1986.
`Hitz, "A System Administrator's Performance Monitor for
`Tuning NFS Network Servers," Auspex Systems, Inc. Tech(cid:173)
`nical Report 7, May 1991.
`Nelson, Benchmark Methodology and Preliminary Perfor(cid:173)
`mance Specifications for the Auspect NS5000 Network
`Server, Auspex Systems, Inc. Technical Report 2, Oct. 1989.
`Nelson, et al., "How and Why SCSI Is Better than IPI for
`NFS," Auspex Systems, Inc. Technical Report 6, 2nd edi(cid:173)
`tion, Jul. 1992.
`Schroder, "PEACE: The Distributed SUPRENUM Operat(cid:173)
`ing System," Parallel Computing, vol. 7 (1988) pp.
`325-333.
`Malcolm, "A Process Abstraction and its Application," Pro c.
`Eighth Manitoba Conference on Numerical Math and Com(cid:173)
`puting, University of Manitoba at Winnipeg, 1978, pp.
`33-50.
`Nelson, et al., "The Myth of MIPS for 1/0: An Overview of
`Functional Multiprocessing for NFS Network Servers,"
`Auspex Systems, Inc., Technical Report 1, 6th edition, 2nd
`printing, Aug. 1992.
`Cheriton, et al., "Thoth, a Portable Real-Time Operating
`System," Communications of the ACM, Feb. 1979, vol. 22,
`No. 2, pp. 102-115.
`Cheriton, "Multi-Process Structuring and the Thoth Oper(cid:173)
`ating System," Ph.D. Thesis submitted to Department of
`Computer Science, University of British Columbia at Van(cid:173)
`couver, 1979.
`Chutani, Sailesh, et al., "The Episode File System",
`USENIX Winter Conference, Jan. 30--24, 1992.
`Sun Microsystems, "Network Programming Guide", Chap(cid:173)
`ter 4, Remote Procedure Call Programming Guide, Revision
`A of 27 Mar. 1990, pp. 65-128.
`Osadzinski, Alex, "The Network File System (NFS)", 8202
`Computer Standards & Interfaces, 8 (1988/89) No. 1, pp.
`45-48, Amsterdam, The Netherlands.
`Tannebaum, AndrewS., "Computer Networks" (1988), 2nd
`Edition, Prentice-Hall, pp. 35, 36, Chap. 9.
`IEEE Computer, "1/0 subsystem", Sep. 1988, pp. 23-25 and
`106.
`Carlson, et al., "HP AdvanceNet: A Growth-Oriented Com(cid:173)
`puter Networking Architectural Strategy", Hewlett-Packard
`Journal (Oct. 1986), p. 2, pp. 6-10.
`Tribby, David M., "Network Services for HP Real-Time
`Computers", Hewlett-Packard Journal (Oct. 1986), pp.
`22-27.
`Motorola, Inc., Microsystems Products Technical Data
`Sheet (1986), MicoMAP1-7, "MicroMAP MAnufacturing
`Automation Protocol Software".
`Hammond, Richard A Expression with the Series/] Distrib(cid:173)
`uted System, Department of Electrical Engineering, U of
`Delaware, Newark, Delaware, © 1980 IEEE.
`Hanson, Per Brinch (editor), brochure: RC 400 Software
`Multiprogramming System, Ch 4: Process Communication,
`Ns Regnecentralen, Copenhagen-Apr. 1969.
`Hartman, John H., et al., The Zebra Striped Network File
`System.
`Hitz, David, Technical Report TROI: An NFS File Server
`Appliance, Network Appliance Corporation.
`
`Microsoft Ex. 1017, p. 2
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`5,819,292
`Page 3
`
`Hitz, Dave et al., Technical Report: 3002: File System
`Design for an NFS File Server ApplianceNetwork Appli(cid:173)
`ance, Jan. 19, 1994.
`Hitz, David, et al., Using Unix as One Component of a
`Lightweight Distributed Kernel for Multiprocessor File
`Servers, Auspex Technical Report 5, ©1990 Auspex Sys(cid:173)
`tems Inc.
`Jones, Anita K., et al., StarOS, a Multiprocessor Operating
`System for the Support of Task Forces, Association for
`Computing Machinery, 1979, pp. 117-127.
`Lantz, Keith A., et al., Rochester's Intelligent Gateway,
`Computer© 1982 IEEE.
`Leffler, et al., The Design and Implementation of the 4.3BSD
`UNIX Operating System, Addison-Wesley, 1989, pp.
`187-245.
`Ousterhout, John, et al., Beating the I/0 Bottleneck: A Case
`for Log-Structured File Systems, Oct. 30, 1988.
`Patterson, David A., et al., A Case for Redundant Arrays of
`Inexpensive Disks (RAID), UC Berkeley.
`Plum, Thomas, Reliable Data Structures in C, section 4.9:
`Pointers to Functions, © 1985 Plum Hall, Inc., pp. 4--23 to
`4-27.
`Rashid, Richard F. et al., Accent: A communication oriented
`network operating system kernel, Department of Computer
`Science, Carnegie-Mellon University, Pittsburgh, PA© 981.
`Ritchie, D.M. The UNIX System: A Stream Input-Output
`System, AT&T Bell Laboratories Technical Journal, Oct.
`1984, vol. 63, No. 8 Part 2, © 1984 AT&T.
`Robertazzi, Thomas G., Computer Networks and Systems:
`Queuing Theory and Performance Evaluation, Ch 1: The
`Queuing Paradigm, © 1990 Springer-Verlag.
`Row, John, Lan Software Links Diverse Machines, OS's,
`Mini-Micro Systems, Sep. 1965, pp. 141-146.
`Row, John, et al., Operating System Extensions Link Dis(cid:173)
`parate Systems, Computer Design, Jul. 1984, pp. 171-183.
`Schwartz, Allan M., et al., LFS-A Local File System for
`Multiprocessor NFS Network Servers, Auspex Technical
`Report 4, © 1989 Auspex Systems, Inc.
`Seltzer, Margo, et al., An Implementation of a Log-Struc(cid:173)
`tured File System for UNIX, 1993 Winter UNIX, San Diego,
`CA.
`
`Seltzer, Margo, File System Performance and Transaction
`Support, 1992.
`Sessions, Roger, Class Construction in C and C++ Object
`Oriented Programming Fundamentals, International Busi(cid:173)
`ness Machines Corporation, section 4.4: Object Method
`Inflexibility, © 1992 Prentice-Hall, NJ.
`Silberschatz, Abraham, et al., Operating Concepts, Ch 3.7:
`Interprocess Communication, pp. 127-147, © 1988 Add(cid:173)
`ison-Wesley Publishing Company, Inc.
`Sincoskie, W., David, et al., The Series! I Distributed Oper(cid:173)
`ating System: Description and Comments, IEEE, 1980, pp.
`579-584.
`Stern, Hal, Managing NFS and NIS, NFS Daemons,© 1991
`O'Reilly & Associates, Inc.
`Tanenbaum, Andrew S., Operating Systems Design and
`Implementation, pp. 251-273.
`Tweten, David, Hiding Mass Storage Under Unix: NASA's
`MSS II Architecture, IEEE, 1990, pp. 140-145.
`Unix System Laboratories, Inc., Unix System V Release 4
`Programmer's Guide: STREAMS, section 2: What is
`STREAMS?, AT & T Unix System Laboratories, Inc., Unix
`System V Release 4 Programmers's Guide: STREAMS.
`1990 Prentice Hall.
`UNIX International, UI-Atlas Distributed Computing Archi(cid:173)
`tecture: A Technical Overview, Oct. 1991.
`VRTX Versatile Real-Time Executive for the Microproces(cid:173)
`sors C: User's Guide, Software Release 1, Document No.
`541331001, Apr. 1987.
`the
`VRTX32!68020 Versatile Real-Time Executive for
`MC68020 Microprocessor: User's Guide, Software Release
`3, Document No. 592103003, Jan. 1987.
`Walton, Robert L., Rational for a Queueable Object Dis(cid:173)
`tributed Interprocess Communication System, IEEE Trans(cid:173)
`actions on Communications, vol. Com-30, No.6, Jun. 1982,
`pp. 1417-1425.
`Wood, B.J., et al.,A Local-Area NetworkArchitecture Based
`on Message-Passing Operating System Concepts, 7th Con(cid:173)
`ference on Local Computer Networks, Miniapolis, MN, Oct.
`1932.
`Sun Microsystems, Inc., Sun OS5.0 Network Interfaces
`Programmer's Guide, p. 108, Jun. 1992.
`
`Microsoft Ex. 1017, p. 3
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 1 of 39
`
`5,819,292
`
`ORIGINAL
`ANODE
`
`110A
`
`110B·
`
`COW BIT 110
`CLEARED
`
`INDIRECT
`BLOCK
`
`DATA
`BLOCK
`. : . - - -
`
`\
`
`114
`
`DATA
`BLOCK
`
`CLONE
`ANODE
`
`120A
`
`120B
`
`120
`
`122
`
`124
`
`DATA
`BLOCK
`
`126
`
`FIG. 1
`PRIOR ART
`
`Microsoft Ex. 1017, p. 4
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 2 of 39
`
`5,819,292
`
`WAFLINCORE
`I NODE
`
`2048
`
`2152
`
`3712
`J
`
`/
`
`222/
`~220
`
`2152
`220A ____.-/
`
`2878
`222A ____.-/
`
`2878
`
`250/
`
`I r
`
`'--250A
`
`3448
`
`230/
`
`240/
`
`3448
`230A ____.-/
`
`3712
`'---- 240A
`
`I
`---~-------------------------------------------
`
`DIRTY INODE
`LIST 210
`
`FIG. 2
`
`ON-DISK
`I NODE
`
`16 BLOCK
`NUMBERS HAVING
`SAME LEVEL OF
`INDIRECTION 310B
`
`ON-DISK
`INFORMATION 310A
`INCLUDING OWNER,
`}
`PERMISSIONS,
`1------,0~---1 ACCESS TIME. ETC.
`1
`
`• • •
`I
`
`• • •
`
`15
`
`• • •
`I
`
`"'-.,__ 310
`
`FIG. 3
`
`Microsoft Ex. 1017, p. 5
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 3 of 39
`
`5,819,292
`
`LEVELO
`I NODE
`
`LEVELO
`I NODE
`
`4-BYTES OF DATA
`4-BYTES OF DATA
`
`• • •
`
`4-BYTES OF DATA
`
`FIG. 4A
`
`310A
`
`64-BYTES
`OF DATA
`4108
`
`DATA
`BLOCK
`
`11}4KBYTES
`~420A
`
`4208
`
`• • •
`~420C
`
`FIG. 48
`
`310
`
`Microsoft Ex. 1017, p. 6
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 4 of 39
`
`5,819,292
`
`LEVEL2
`I NODE
`
`310A t
`
`PTRO
`PTR 1
`•
`• •
`
`I
`
`31081
`
`310
`
`DATA
`BLOCK
`
`} 4KB
`440A
`
`~4408
`
`440C
`
`•
`•
`•
`
`INDIRECT
`BLOCK
`
`430A
`
`4308
`
`0
`1
`•
`•
`•
`1023
`
`0
`1
`
`• • •
`
`1023
`
`0
`1
`
`• • •
`
`1023
`
`430C
`
`FIG. 4C
`
`Microsoft Ex. 1017, p. 7
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`-490F
`
`'0
`~
`......,
`0
`Ul
`.....
`=-
`
`~
`~
`
`'Jl
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`=
`
`......
`~
`......
`~
`~
`•
`\Jl
`d •
`
`.. ~490E
`Q_490D
`
`I (
`
`•
`•
`1
`0
`
`FIG. 40
`
`470C
`
`I
`
`1L
`H
`
`470B
`
`•
`•
`•
`
`-~490C
`
`•
`•
`•
`
`-~490B
`
`490A
`}4KB
`
`BLOCK
`DATA
`
`INDIRECT
`SINGLE-
`
`BLOCK
`
`•
`•
`•
`
`1023
`•
`•
`•
`1
`0
`
`'\
`
`\
`
`480A
`
`\
`
`•
`•
`•
`
`I
`I
`I
`
`\
`
`1-----------------------------.
`
`1023
`•
`•
`•
`1
`0
`
`I
`
`~
`
`•
`•
`•
`
`'\
`
`1023
`•
`•
`•
`1
`
`I~ 0
`
`310
`
`1-,_
`
`PTR 15
`
`•
`•
`•
`
`PTR 1
`PTRO
`
`310B ~ I
`
`310A -~ I
`
`INDIRECT
`DOUBLE-
`
`BLOCK
`
`I NODE
`LEVEL3
`
`Microsoft Ex. 1017, p. 8
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 6 of 39
`
`5,819,292
`
`MARK ALL "DIRTY"
`510 ~ INODESAS IN
`CONSISTENCY
`POINT
`l
`FLUSH
`520 _/ REGULAR FILES
`1
`
`530 ""-
`
`FLUSH
`META-DATA FILES
`1
`FLUSH
`540 _/ FSINFO BLOCK
`l
`
`PROCESS INODES
`THAT WERE NOT
`_/ IN CONSISTENCY
`550
`POINT
`
`FIG. 5
`
`530~
`
`610 ~
`
`PRE-FLUSH THE
`INODES OF THE
`BLKMAP FILE
`1
`WRITE-ALLOCATE
`_/ DISK SPACE FOR
`620
`ALL Dl RTY BLOCKS
`1
`FLUSH THE
`INODE FOR THE
`BLKMAP FILE
`!
`UPDATE ENTRIES
`IN BLKMAP FILE
`~
`WRITE DIRTY
`BLOCKS IN
`650 _/ BLKMAP AND INODE
`FILES TO DISK
`
`630
`""-
`
`640 _/
`
`FIG. 6
`
`Microsoft Ex. 1017, p. 9
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 7 of 39
`
`5,819,292
`
`r------------------------- 1
`
`PRE-FLUSH THE
`INODES OF THE
`710 ~ BLKMAP FILE
`AND THE
`SNAPSHOT
`!
`DIRTY EVERY
`BLOCK IN THE
`BLKMAP FILE
`
`720 _/
`
`!
`WRITE-ALLOCATE
`730
`"-- DISK SPACE FOR
`ALL DIRTY BLOCKS
`
`!
`
`530~
`I
`
`_/
`740
`
`COPY ROOT
`INODE OF FILE
`SYSTEM INTO
`SNAPSHOT INODE
`
`!
`
`750 _/
`
`FLUSH THE
`INODE FOR THE
`BLKMAP FILE
`AND SNAPSHOT
`
`!
`
`760 "--
`
`UPDATE ENTRIES IN
`BLKMAP FILE BY
`COPYING FS-Bn
`INTO CP-BIT AND
`SNAPSHOT BIT
`
`770 "--
`
`!
`
`WRITE DIRTY
`BLOCKS IN
`BLKMAPAND
`INODE FILES
`TO DISK
`
`FIG. 7
`
`Microsoft Ex. 1017, p. 10
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 8 of 39
`
`5,819,292
`
`INCORE
`I NODE
`
`WAFL BUFFER
`DATA STRUCTURE
`820A
`
`16 POINTERS HAVING
`SAME LEVEL OF
`INDIRECTION 8208
`
`• • •
`
`0
`1
`
`• • •
`
`PTR 15
`
`INCORE
`INFORMATION 820C
`INCLUDING DIRTY FLAG,
`IN-CP FLAG, LINKED
`LIST POINTER(S)
`
`}
`:J
`
`• • •
`
`820
`
`} ON-DISK
`INODE 310
`
`FIG.B
`
`Microsoft Ex. 1017, p. 11
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 9 of 39
`
`5,819,292
`
`310A,
`310B
`820A
`
`64-BYTES
`OF DATA
`920B
`
`LEVEL 0
`I NODE
`
`4-BYTES OF DATA
`4-BYTES OF DATA
`
`• • •
`
`4-BYTES OF DATA
`820_r
`
`FIG. 9A
`
`310A,
`3108,
`820A
`
`820B
`
`LEVEL 1
`I NODE
`
`PTRO
`PTR 1
`
`• • •
`
`820
`
`• • •
`
`DATA (DIRECT)
`BUFFER
`
`11}4KBYTES
`~922A
`
`9228
`
`• • •
`~922C
`
`FIG. 98
`
`Microsoft Ex. 1017, p. 12
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 10 of 39
`
`5,819,292
`
`940C
`
`310A,
`3108,
`820A
`
`8208
`
`LEVEL2
`I NODE
`
`PTRO
`PTA 1
`
`• • •
`
`PTA 15
`
`820
`
`INDIRECT
`BUFFER
`
`930A
`
`• • •
`
`9308
`
`0
`1
`
`• • •
`
`1023
`
`0
`1
`
`• • •
`
`1023
`
`• • •
`
`0
`1
`
`• • •
`
`1023
`
`930C
`
`FIG. 9C
`
`Microsoft Ex. 1017, p. 13
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`
`"""' 0 ......,
`"""'
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`~990F
`
`• • •
`
`-o'--990E
`
`990D
`
`990C
`
`• • •
`
`h
`• • •
`
`-0'--990B
`
`990A
`}4KB
`
`BUFFER
`
`DATA
`
`.
`
`---
`
`FIG. 90
`
`980B
`
`• • •
`
`1
`0
`
`• • •
`
`• • •
`
`1
`0
`
`BUFFER
`INDIRECT
`SINGLE-
`
`--------
`
`-
`
`• • •
`
`970C
`
`1023
`
`• • •
`
`1
`0
`
`:
`
`970B
`
`1023
`
`• • •
`
`1
`0
`
`,~70A
`
`1023
`
`• • •
`
`1
`0
`
`BUFFER
`INDIRECT
`DOUBLE-
`
`..A'I
`
`• • •
`
`"
`
`I
`
`820
`r
`
`• • •
`
`PTR 1
`PTRO
`
`I NODE
`LEVEL 3
`
`820B ~ I
`
`'>
`
`~
`
`820A
`310B,
`310A,
`
`Microsoft Ex. 1017, p. 14
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 ......,
`"""" N
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`""""
`'0
`~~
`:-'"
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`----------------------1
`
`1034B
`
`• •
`
`----_I
`
`---1o32--=.7------__ _
`
`e
`
`I
`I
`
`BUFFER
`
`4KB
`
`-----------:
`
`1032B-------.
`
`1032A
`
`I
`r--
`
`BUFFER
`
`4KB
`
`\_1
`l r----------------------
`
`1030B
`
`WAFL BUFFERS
`
`DIRECT
`
`1030
`
`I
`
`1034--=.7----·-------
`
`-
`
`FIG. 10
`
`-----------------
`I
`
`I
`
`BUFFER
`
`4KB
`
`-----1
`
`-----------
`
`•
`
`• •
`
`~----------------~
`
`I
`I
`
`---------------\-__ I
`
`----1
`
`--
`
`-
`
`D ~~022
`,---------D : 1020
`
`1 020C_..-/ NUMBERS
`
`BLOCK
`
`~ 1024 ON-DISK
`STRUCTURE ~ 4KB
`
`1020A
`. )___.
`
`1024-WAFL
`
`POINTERS
`BUFFER
`
`4KB
`
`BUFFER
`
`STRUCTURE
`WAFLBUFFER
`
`WAFL BUFFERS
`
`INDIRECT
`
`INODE
`
`1010A--------
`
`WAFLINCORE
`
`1010
`
`I NODE
`ON-DISK
`POINTERS
`16 BUFFER
`STRUCTURE
`1010C~ ~WAFLBUFFER
`
`1010B
`
`INFORMATION
`
`Microsoft Ex. 1017, p. 15
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 13 of 39
`
`5,819,292
`
`BLKMAP
`FILE
`
`,-----------
`I ~1110A
`I
`
`1
`
`- ~
`
` 1110C
`
`BLKMAP
`ENTRY
`
`I
`I
`!
`c
`__.,/"
`1110B
`
`-------
`
`• • •
`
`~ 11100
`
`1110
`FIG. 11A
`
`CP-BIT
`
`SNAPSHOT BITS (BIT 1 - BIT 20)
`
`111 OA
`
`UPPER 11 BITS (BIT 21- BIT 31}
`ARE RESERVED
`
`FIG. 118
`
`0
`
`0
`
`0
`
`0
`
`•••
`
`o I o
`
`0
`
`FREE BLOCK
`
`FIG. 11C
`
`0
`
`0
`
`0
`
`0
`
`•••
`
`0
`
`I o
`
`y
`
`BLOCK IN
`ACTIVE FILE SYSTEM
`
`FIG. 110
`
`FS-BIT
`
`1110A
`;
`o I
`
`1110A
`
`BITO;
`
`Microsoft Ex. 1017, p. 16
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 14 of 39
`
`5,819,292
`
`I NODE
`FILE
`-
`
`1210A
`·~
`INCORE
`(ON-DISK)
`I NODE
`820 (310)
`
`{
`
`1210
`
`I
`I
`
`4 KB
`BUFFER 1220
`(BLOCK)
`
`• • •
`
`__/
`12108
`
`__/
`1210C
`
`__/
`1210D
`
`__/
`1210E
`
`....-- :----_......
`
`• • •
`
`1210F
`
`FIG. 12
`
`FIXED {
`LENGTH
`ENTRY
`
`1412
`
`1414
`
`VARIABLE {
`LENGTH
`ENTRY
`1416
`
`1412A
`
`14128
`
`\
`HASH POINTER
`VALUE
`
`1410
`
`DIRECTORY
`
`• • •
`
`1410A
`
`"DIRECTORY _ABC"
`
`14108
`
`• • •
`
`1418
`
`FIG. 14
`
`Microsoft Ex. 1017, p. 17
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 15 of 39
`
`5,819,292
`
`1310A /
`
`13108 /
`
`1310C /
`
`1310
`
`INOMAP
`FILE
`
`32
`
`} 8-BITS
`
`5
`
`• • •
`
`0
`
`FIG. 13A
`
`I NODE
`FILE
`
`4 KB
`BLOCK
`
`INOMAP
`FILE
`32
`5
`•
`•
`•
`0
`
`1350A
`~
`13508 /
`
`/
`1350C
`
`1350
`
`1340
`
`/~
`
`/
`
`¥"' 1340A /
`-...
`13408
`~
`
`0
`1
`
`• • •
`
`31
`
`' '>1..
`
`1340C /
`
`FIG. 138
`
`Microsoft Ex. 1017, p. 18
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 16 of 39
`
`5,819,292
`
`FSINFO
`BLOCK
`
`1510C '-----..
`CHECKSUM
`1510D / GENERATION COUNT
`
`MISCELLANEOUS
`DATA 1510A
`
`• • •
`
`INODE OF
`INODE FILE
`1510B
`
`1510
`
`FIG. 15
`
`--------------------------------------------
`
`1
`
`v2306A : /
`23068
`
`vCPFLAG
`2391
`
`0
`•
`
`0
`•
`
`I
`I
`I
`l ____________________ \ ( _____________________ l
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`v:-
`
`CP FLAG
`2392
`
`~ LIST 2390 OF
`INODESWITH
`DIRTY BUFFERS
`
`FIG. 17A
`
`: /
`v2306A
`2306B
`
`1
`1
`•
`•
`_________________ /' _______________________ _
`
`v2391
`
`,_/
`2392
`
`LIST 2390 OF
`INODESWITH
`DIRTY BUFFERS
`
`/
`
`FIG. 171
`
`Microsoft Ex. 1017, p. 19
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 17 of 39
`
`5,819,292
`
`r-------------------------------------------------- 1
`FSINFO
`1610 ~ FSINFO
`1612 ~
`~1612A
`..---'-----, \
`1612C ~~-=-:-:-==-=-~,....,...j--'
`161 OB / CHECKSUM MISCELLANEOUS :
`CHECKSUM
`DATA 1610A
`
`1 - - - - - - - t / 16128
`
`INODE 1610AOF
`INODE FILE 1620
`
`• • •
`
`• • •
`
`( I NODE
`FILE
`
`j
`
`• • •
`
`• • •
`
`BLKMAP FILE
`
`v164o
`
`INOMAP FILE
`
`INODE 1620A
`OF BLKMAP
`FILE 1630
`
`INODE 16208
`OF INOMAP
`FILE 1640
`
`INODE 1620C
`OF ROOT
`DIRECTORY
`1650 OF
`FILE SYSTEM
`
`PLURALITY
`OF INODES
`FOR FILES
`IN THE
`FILE SYSTEM
`
`• • •
`• • • V 1620D
`1---~------
`• • •
`• • •
`- - ---------. -• • •
`l
`
`r-----1650
`~---"---1
`
`ROOT
`DIRECTORY
`
`TYPICAL
`FILE OR
`DIRECTORY
`
`I
`
`}
`
`L - - - - - - -1
`
`I
`~----------------------1
`I
`I
`I
`I
`I
`I
`
`~ FILE SYSTEM 1670
`
`1620
`
`I
`----------------------------~
`
`FIG. 16
`
`Microsoft Ex. 1017, p. 20
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`"""' ~
`0
`'"""' 00
`~ ....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`~-0---_-_-_-_-_-_-_-_-_-_:V BLKMAP
`
`2344
`FILE
`
`:
`~ :
`
`' ·------------
`:
`
`2324
`
`' ' ' '
`: 2314
`VFILE2340
`' ~2312
`
`~FILE 2342
`'
`'
`
`:__
`
`2316
`
`;---------------.
`-----------(cid:173)
`
`~
`
`'
`
`/in ~ mH-2310
`
`FIG. 178
`
`•-----------------------·
`'
`' '
`
`'
`
`2344
`2342
`2340
`
`• • •
`
`2304
`BLOCK
`4 KB
`
`'
`
`2346
`INODE FILE
`
`: -r-------,
`'
`
`-------------------!_(cid:173)
`
`2306
`
`2306G
`2306B
`2306A
`
`I NODE
`ROOT
`
`2302
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 21
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 ......,
`'"""'
`'0
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`'
`~FILE 2342
`' ' '
`
`v~2320
`
`1
`
`10
`: ---------VBLKMAP
`
`2344
`FILE
`
`, _____________ J
`'
`:
`!
`
`4
`
`2316
`
`FIG. 17C
`
`232
`
`-----------------------1
`
`2344
`2342
`2340
`
`• •
`
`•
`
`I
`
`2306 ...../:
`
`2306C
`2306B
`2306A
`
`2304
`BLOCK
`
`! I
`' '
`'
`! 14 KB
`' '
`' ' '
`'
`y
`:
`'
`:
`'
`--··--------________ ;_ --,
`2346
`INODE FILE
`
`I ~ ~-
`
`-
`
`I NODE
`ROOT
`
`.
`
`2302
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 22
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 20 of 39
`
`5,819,292
`
`BIT 31
`(CP-BIT)
`~ 1
`~ 1
`~ 0
`~ 1
`~ 1
`~ 1
`~ 1
`~ 1
`~ 1
`~ 0
`~ 1
`~ 0
`~ 0
`
`2304
`2306
`2308
`2310
`2312
`2314
`2316
`2318
`2320
`2322
`2324
`2326
`2328
`
`.__
`
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`• • •
`
`BIT 1 BITO
`(FS-BIT)
`~ 2324A
`/ 2324B
`~ 2324C
`/ 23240
`/ 2324E
`2324F
`/
`~ 2324G
`/ 2324H
`23241
`/
`2324J
`/
`~ 2324K
`2324L
`/
`/ 2324M
`
`1
`1
`0
`1
`1
`1
`1
`1
`1
`0
`1
`0
`0
`
`1
`1
`0
`1
`1
`0
`1
`1
`1
`0
`1
`0
`0
`
`-
`
`FIG. 170
`
`BIT 31
`(CP-BIT)
`
`1
`0
`1
`1
`1
`0
`1
`1
`0
`1
`0
`1
`
`BLOCK #
`2304
`2306
`2308
`2310
`2312
`2314
`2316
`2318
`2320
`2322
`2324
`2326
`2328
`
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`•••
`• • •
`
`1
`1
`0
`1
`1
`1
`1
`1
`1
`0
`1
`0
`
`BIT 1 BITO
`(FS-BIT)
`v
`v
`v v
`v
`v
`v
`v
`v
`v
`v v
`
`2326A
`2326B
`2326C
`23260
`2326E
`2326F
`2326G
`2326H
`23261
`2326J
`2326K
`2326L
`
`1
`0
`1
`1
`1
`0
`1
`1
`0
`1
`0
`1
`
`-....
`
`FIG. 17J
`
`4 KB
`BLOCK
`2324
`
`4 KB
`BLOCK
`2326
`
`Microsoft Ex. 1017, p. 23
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`
`'"""' 0 .....,
`~ ....
`'JJ. =(cid:173)~
`
`N
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`JO VBLKMAP
`~---__ -_-_-_-_-_-_-_-_Y Fl LE 2342
`
`• _____________ j
`:
`2344
`'
`: FILE
`
`2324
`
`~2320
`'
`
`:-2318
`
`2316
`
`'
`' VFILE2340
`'
`i---2312
`
`*
`2314
`
`·-~2310
`'
`'
`;-------------.
`
`FIG. 17E
`
`I*
`
`2308C~
`23088
`2308A~
`
`• •
`•
`2342
`
`2308
`
`•--------------
`'
`' '
`'
`2306C
`'
`'
`23068
`:
`2306A:/1:
`
`2306
`
`2304
`BLOCK
`4 KB
`
`/~ i
`
`2346
`INODE FILE
`
`-------------------/_-'
`
`/
`
`2302
`
`I NODE
`ROOT
`
`BLOCK*
`FSINFO
`
`Microsoft Ex. 1017, p. 24
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 .....,
`N
`N
`
`~ ....
`'JJ. =(cid:173)~
`
`00
`'0
`""""
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`;n VBLKMAP
`~~FILE2342
`. I E r:
`
`.
`2344
`! FILE
`
`2324
`
`~-----------,
`
`'
`
`-----
`
`'-------
`'
`
`I
`
`: 2320
`
`}-.-2318
`
`:
`
`2316
`
`***
`2322
`
`*
`2314
`
`,
`;-------------'
`
`FIG. 17F
`
`*
`
`• • •
`
`23080
`2308C
`2308B
`2308A
`
`2304
`BLOCK
`4 KB
`
`2346
`INODE FILE
`
`-----------------_/
`
`' ,.--------,
`'
`
`I NODE
`ROOT
`
`2302
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 25
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 ......,
`~
`N
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`
`~ ......
`~
`•
`\Jl
`d •
`
`FIG. 17G
`
`~~326
`
`~-----------,
`
`' '
`: _____________ _
`~FILE2342
`'
`~2320
`
`'
`~2318
`
`:-2316
`
`*
`2314
`
`,-------------
`
`;o VBLKMAP
`
`. _____________ J
`*
`:
`2344
`'
`: FILE
`
`2324
`
`'*
`
`• • •
`
`--
`
`--
`
`--
`
`I
`
`2308-----
`
`2308C
`2308B
`2308A
`
`2306
`
`i
`2306C
`2306B
`'
`2306A:/j:
`
`2304
`BLOCK
`4 KB
`
`·~------,
`'
`
`------------------I
`
`2346
`INODE FILE
`
`I NODE
`ROOT
`
`2302
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 26
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`**
`2326
`
`'
`
`2324
`
`~------------------~
`
`'0
`"""' ~
`
`0
`~
`N
`
`~ ....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`:
`2344
`: FILE
`V BLKMAP
`: FILE 2342
`~
`
`I
`
`I
`
`,
`: I E
`
`----..__
`
`:-2318
`
`2316
`
`*
`2314
`~FILE2340
`'
`i.--2312
`' '
`:
`
`1--------------
`,
`
`A
`
`~~~-----------: 2310
`
`"--.._ ~· : 2320
`
`n=J
`,
`
`F
`
`:
`
`I
`
`~.
`
`"'
`
`~. :______
`
`FIG. 17H
`
`•**
`
`• •
`
`2308
`
`2308C
`2308B
`2308A.-/
`
`2344
`2342
`2340
`
`• • • --
`
`--
`
`2304
`BLOCK
`4 KB
`
`' : -"".---------,
`------------------)_
`
`2346
`INODE FILE
`
`I NODE
`ROOT
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 27
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 ......,
`Ul
`N
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~~
`!"""
`I")
`0
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`~-----------,
`
`18!"--FILE 2342
`
`: ____ --------
`'
`'
`
`?0 VBLKMAP
`
`***
`2326
`
`:
`2344
`: FILE
`
`·-----
`'
`
`2324
`
`I : 2320
`
`' :-2318
`
`:-2316
`
`E
`
`: I
`
`FIG. 17K
`
`I***
`
`• • •
`
`----
`
`2344
`2342
`2340
`
`• • •
`
`I
`
`2308---'
`
`2308C
`2308B
`2308A.-/
`
`--
`
`*
`2314
`~FILE 2340
`
`•-------------~
`,
`
`!Al{' 2310
`
`'
`'
`'
`
`t"' ~
`1 )---2312
`
`B
`
`2304
`BLOCK
`4 KB
`
`2346
`INODE FILE
`
`' '
`'
`
`'
`
`-----------------_/ -,
`
`I NODE
`ROOT
`
`BLOCK
`FSINFO
`
`Microsoft Ex. 1017, p. 28
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`N
`\C
`N
`....
`\C
`~
`00
`....
`Ul
`
`'0
`~
`0 ......,
`0'1
`N
`~ .....
`'JJ. =(cid:173)~
`
`00
`'0
`'"""'
`'0
`~0'1
`!"""
`I")
`0
`
`~ = ......
`
`~ ......
`~
`•
`\Jl
`d •
`
`~2324
`
`FILE 2342
`
`.~2320
`--------_ _:
`
`~
`~2318
`
`:-2316
`
`***
`2322
`
`***
`
`.-------------1
`
`2304
`BLOCK
`4 KB
`
`'
`' ' '
`---------------------I_(cid:173)
`
`2346
`INODE FILE
`
`FIG. 17L
`
`-------------------------
`' '
`
`***
`
`• • •
`
`2308
`
`2308C
`2308B
`2308A
`
`2306
`
`2306C
`2306B
`2306A
`
`***
`
`I NODE
`ROOT
`
`2302
`
`BLOCK
`FSINFO
`
`JO
`' -------------V BLKMAP
`
`~
`'
`t
`:
`2344
`, FILE
`
`----------
`'
`*** 1
`
`2326
`
`Microsoft Ex. 1017, p. 29
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 27 of 39
`
`5,819,292
`
`1810
`
`FSINFO
`BLOCK
`
`FIG. 1BA
`
`1816
`
`1818
`
`1820
`'
`~1830
`-------------f
`
`1810
`
`~---------1
`
`FSINFO
`BLOCK
`
`I
`I
`
`I 1812
`I
`I 1814
`I
`I 1816
`I
`I 1818
`
`SNAPSHOT
`I NODE
`
`FIG. 188
`
`Microsoft Ex. 1017, p. 30
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 28 of 39
`
`5,819,292
`
`1810
`
`.-- - - - -- - - - -I
`
`FSINFO
`BLOCK
`
`INODE 1810A {
`OR INODE FILE
`
`1818
`
`I
`
`1820
`
`I
`0fi1824
`
`I
`
`I
`~1830
`
`SNAPSHOT
`I NODE
`
`I
`I ____________________________ I
`
`FIG. 1BC
`
`Microsoft Ex. 1017, p. 31
`Microsoft v. Daedalus Blue
`IPR2021-00831
`
`

`

`U.S. Patent
`
`Oct. 6, 1998
`
`Sheet 29 of 39
`
`5,819,292
`
`INODE OF
`INODE FILE
`
`1824
`~----------------------~--------------
`
`1
`
`~/0~0~h
`1
`
`• • •
`
`15
`
`•
`
`D'
`
`I
`1820
`
`('-------'
`NEW BLOCK
`1910
`
`1922
`
`! __ __ __ ___ ___ __ __ _ __ _ __ _ _
`
`DOUBLE(cid:173)
`INDIRECT
`BLOCKS
`
`SINGLE(cid:173)
`INDIRECT
`BLOCKS
`
`DIREC