KR20110127636A - How to manage downloads of discardable files - Google Patents

Abstract

A request is received to store a file in a storage area of a storage device, the file being discardable, associating the file with data in a data structure associated with the storage device. The file is marked as discardable. In some implementations, the file system structure of the data structure is indicated so that the file represents a discardable file, and in other implementations, the file itself is indicated to indicate that the file is a discardable file. The download manager determines a download state associated with the request to store the discardable file in the storage area of the storage device, and determines whether to delay the download of the discardable file to the storage device based on the determined download state. The download manager manages the download of the discardable file on the storage device based on the determination of whether to delay the download of the discardable file on the storage device.

Description

How to manage downloads for discardable files {DOWNLOAD MANAGEMENT OF DISCARDABLE FILES}

Priority claim

This application is directed to both U.S. Provisional Patent Application No. 61 / 159,034 filed on March 10, 2009 and U.S. Provisional Patent Application No. 61 / 259,418, filed on November 9, 2009. Claimed benefit, the entire contents of each of which are incorporated herein by reference.

The present invention relates generally to storage devices, and more particularly to methods and apparatus for managing files in storage devices.

Non-volatile storage devices are portable and physically small in size and large in storage capacity, and their use has been increasing rapidly for many years. Storage devices come in a variety of designs. Some storage devices are considered "embedded", meaning that they cannot and cannot be removed by a user from the host device on which they operate. Other storage devices are removable, meaning that a user can move from one host device (eg, a digital camera) to another, or replace one storage device with another.

Digital content stored on a storage device may originate from a host of the storage device. For example, it captures a digital camera, host, and image and converts it to the corresponding digital data. The digital camera then stores the digital data in a storage device that operates with it. Digital content stored on a storage device may originate from a remote source, which may be sent to a host of the storage device, for example, via a data network (eg, the Internet) or a communication network (eg, a cellular telephone network). And may then be downloaded to the storage device by the host. The remote source can be, for example, a service provider or a content provider. Service providers and content providers are collectively referred to as "publishers" below.

As storage devices within mobile handsets increase in size and capacity, there may be new scenarios for content acquisition and consumption on an ongoing basis. Typically, the handset is downloaded from a server controlled by the operator, a market application such as Apple's iTunes service, and can be used to consume side-loaded movies and music from sources such as SanDisk's slot media cards. However, in all these applications, the user must pre-search ahead for the content he wants to consume, authorize the acquisition of the content to authorize, acquire the content and then consume it. This reduces the ability of the content owner to provide content for consumption on the fly and the ability for the user to immediately see what they are getting without waiting for download.

Many prototypes have preloaded content to the user, but they all have one common drawback. In other words, the user must sacrifice his storage capacity to store the content, but cannot access the content until it is purchased. Users who have to purchase this capacity generally do not want to see most of them assigned to content that is not actually available to them.

A user of a storage device can voluntarily download media content and advertisements by requesting media content or advertisements from publishers. Oftentimes, however, publishers to increase their income do not ask the user for their permission, and often send this content without the user knowing that the content has been downloaded to the user's storage device. The content that the publisher sends to them without obtaining the user's consent is referred to herein as " unsolicited content. &Quot; Often, unsolicited content is intended to be consumed by a user after or after paying a publisher.

By downloading unsolicited content to the user's storage device, the publisher wants to increase their income by eventually paying for the content and consuming unsolicited content. The practice of storing content that the publisher wants to consume and consume for this content but does not require the user's consent and requires the storage device is a concept known as "predictive consignment" in the media publishing field. However, unsolicited content may be present by the user of the storage device, or may not want to consume it and may remain stored on the storage device. Storing content that is not required by the storage device reduces the user storage space available (ie, free) to the storage device, which is undesirable from the user's point of view. The user has run out of storage space for his or her content (e.g. music files) or deleted content that he did not require because someone (ie some publisher) has taken up some of the storage space on the storage device. The user may find that the user may need to reclaim the storage space taken.

One partial solution to the problem of taking up a portion of a user's storage space includes blocking the publisher's access to the storage device, such as by blocking the publisher's website. This solution may be acceptable to the user, but is problematic for the issuer because the issuer will rarely make a sale and will lose its potential source of income. Another partial solution to this problem involves publishing content to a host (saving the content file on the storage device of these hosts) and removing the content when it becomes irrelevant. That is, the publisher who created the content removes this stored unsolicited content from the storage device when the content becomes irrelevant. Unsolicited content is considered irrelevant when time for its consumption has elapsed or when there is an indication that the user will not consume it.

Accordingly, there is a need for a new technology for wisely managing handset storage so that content owners can put content on the handset while the user can be left free to use their storage without penalty. Therefore, there is a need to reduce the problem caused by undesired files by reducing. Specifically, while the publishers are downloading content that is not required by the storage device in the course of performing their tasks, the downloader should not allow the user to substantially quit the download.

Therefore, while the storage space needed to accommodate files not required by the storage device is not required for the user's files, they are stored on the storage device and stored to ensure the minimum amount of free storage space for the user files. It would be an advantage if you could remove files you do not require from your device. Various embodiments are designed to implement such file management, examples of which are provided herein.

To solve the foregoing, a file stored on a storage device, or a file to be stored, is marked as non-disposable or discardable in the structure of the file system associated with the storage device. Each marked file associates it with a discard priority level. New publisher's files (i.e. files that are not required) are only stored on the storage device if saving them to the storage device does not narrow the storage usage safety margin reserved for user files beyond the desired margin. Is allowed. On the other hand, user files are allowed to be stored on the storage device even though their storage narrows the storage usage safety margin beyond the desired width. In this case, however, the desired width of the storage use safety margin is recovered by removing one or more discardable files from the storage device. A discardable file is removed from the storage if its discard priority level is equal to or higher than the predetermined discard threshold (or lower, as described herein).

In some implementations, the download manager, which may be part of the storage allocator (these two may be on the host, the storage device, or a combination thereof) manages discardable downloads in the storage area of the storage device based on one or more download states. do. A request is received to store a file in a storage area of a storage area of a storage device, the file being a discardable file and associating the file with data in a data structure associated with the storage device. In some implementations, the data structure can include a file system structure associated with the storage device. The file is marked as discardable. In some implementations, the file system structure of the data structure associated with the discardable file is indicated to indicate that the file is a discardable file. In another implementation, the file itself is marked as discardable.

The download manager determines a download state associated with the request to store the discardable file in the storage area of the storage device, and the download manager determines whether to delay the download of the discardable file to the storage device based on the determined download state. The download manager manages the download of the discardable file on the storage device based on the determination of whether to delay the download of the discardable file on the storage device. In some implementations, the download manager can delay the download of the discardable file to the storage device until a parameter associated with the download state is satisfied. A storage allocator, which may include a download manager, manages the storage of downloaded discardable files in a storage area of the storage device based on indicating that the file is a discardable file.

Many illustrative embodiments have been shown in the accompanying drawings with the intention that such examples are not limiting. It is to be understood that the elements shown in the drawings referred to below are not necessarily drawn to scale for simplicity and clarity of illustration. Also, the same reference numerals may be used in the drawings when considered to be suitable.

The present invention has the effect of providing a method and apparatus for managing files in a storage device.

1 is a block diagram of a storage system according to an embodiment.
2 is a block diagram of a storage system according to another embodiment.
3 is a block diagram of a storage allocator in accordance with an embodiment.
4 is a method of managing a file according to an embodiment.
5 is a method for managing storage of discardable files in accordance with an embodiment.
6 is a method for displaying one or more unsolicited files in a FAT32-structured file system in accordance with an embodiment.
7 is a directory area associated with a FAT32 table.
8 is a FAT32 table according to the embodiment.
9 is an NTFS table according to an embodiment.
10 is a logical image of a FAT-based file system in accordance with an embodiment.
11 illustrates a file storage management method according to the present disclosure.
12A shows a primary FAT.
12B illustrates a disposable FAT.
13 is a flowchart of a method of managing a storage device using a primary FAT and a disposable FAT.
14 is a flowchart of a method of managing a storage device using a primary FAT and a database.
15 is a flowchart of a method of managing a storage device using FAT and location files.
FIG. 16 illustrates a FAT including a cluster chain in which an order of two or more clusters including a cluster chain is scrambled. FIG.
FIG. 17 illustrates a FAT and associated location file containing a cluster chain in which the order of two or more clusters including the cluster chain is scrambled.
FIG. 18 is a flow chart of a method for managing storage using FAT scrambled order of two or more clusters comprising cluster chains. FIG.
19 is a flow diagram of a method for using a transition lock to prevent the conversion of a discardable file when the discardable file is open in a file system implementing primary and discardable FAT.
20 illustrates that bits mask user IDs in a file system.
21 illustrates the client side components of the smart cache.
FIG. 22 illustrates a file system structure for discardable files modified for Smart Cache HD. FIG.
23 is a block diagram of a large file manager for use in a smart cache HD system.
24 is a conversion flow diagram for a large discardable file.
25 is a flowchart illustrating a method of processing a switch request by a large file manager.
FIG. 26 illustrates a Matroska file structure as an example of a file that can be divided. FIG.
27 shows a divided Matroska file.
28 is a flowchart of a method of managing download of discardable files in a storage area of a storage device.

The following description provides various details of example embodiments. However, this description is not intended to limit the scope of the claims, but instead to describe various principles of the invention and how to practice it.

To solve unsolicited content and related issues, user files are given a storage priority for other files, and a storage usage safety margin is maintained to guarantee this priority. A "user file" is a file that a user of a storage device voluntarily stores or authorizes storage on a storage device. For example, a music file that a user downloads to his storage device is considered as a user file. When requested or approved for storage by a user, the user file is considered a "requested" file.

"Other files" are referred to herein as "issuer files" and "unsolicited files." A "issuer file" is a file stored on a storage device that the user has not requested or that has not known it for at least a while. You may not want to use a file that you do not require. Unused files tend to consume expensive storage space on the user's storage device. Therefore, in accordance with the principles disclosed herein, such files are allowed to be stored on the storage device only if storing them does not narrow the storage use safety margin. The storage priority is given to the user file by maintaining free storage space (ie, storage usage safety margin) to be reserved for the user's file in the future. A storage use safety margin must be maintained to ensure that user files are stored on the storage device whenever required or desired.

If for some reason the storage use safety margin becomes narrower than desired, one or more unsolicited files will be removed (ie, deleted) from the storage device to restore the storage use safety margin. Maintaining a storage usage safety margin guarantees storage space for additional user files if these files are downloaded to the storage device. To this end, unsolicited files are marked “disposable” in the structure of the storage file system and, if required, are later removed to reclaim at least the free storage space required to maintain a storage usage safety margin.

Because the likelihood that a user may use various disposable files may vary from one disposable file to another, each unsolicited file (ie, each disposable file) may be associated with the probability of using the file in advance, and the use of the file. Revocation priority levels are assigned according to one or more criteria, such as revenue present, file size, file type, file location, file storage period, and the like. For example, the revocation priority level can be determined by the profit potential. According to another example movie trailers or advertisements will have a higher discard priority than actual movies because the user generally does not want to see trailers and advertisements. According to another example, one or more discardable files most likely to be used by a user are assigned the lowest discard priority level, which means that these files will be the last file (s) to be removed from the storage device. In other words, the higher the probability of using a discardable file, the lower the level of discard priority assigned to this file. If one or more discardable files have been removed and the desired storage use safety margin is not fully recovered, additional disposable files will be removed from the storage device until the desired storage use safety margin is restored.

Briefly, data structures such as file systems implement a method of storing and organizing computer files. The file system includes a set of Appact data types and metadata implemented for storage, hierarchical organization, manipulation, navigation, access, and retrieval of data. Abtract data types and metadata form a "directory tree" through which computer files (herein referred to as "data files" or simply "files") can be accessed, manipulated, and invoked. . A "directory tree" typically includes a root directory and an optional sub-directory. The directory tree is stored in the file system as one or more "directory files". A set of metadata and directory files contained in a file system is referred to herein as a "file system structure." Therefore, the file system includes data files and file system structure that facilitates accessing, manipulating, updating, deleting, and starting data files.

The file allocation table ("FAT") is a representative file system architecture. The FAT file system is used in a variety of operating systems including DR-DOS, OpenDOS, MS-DOS, Linux, Windows, and the like. The FAT-structured file system uses a centralized table of information about which storage areas are emptied and allocated and where each file is stored on the storage device. To limit the size of the table, storage space is allocated to files in groups of contiguous sectors called "clusters." As storage has evolved, the maximum number of clusters has increased and the number of bits used to identify the cluster has increased. The FAT format version is derived from the number of table bits: FAT12 uses 12 bits, FAT 16 uses 16 bits, and FAT32 uses 32 bits.

Another file system architecture is known as the New Technology File System ("NTFS"). Currently, NTFS is the standard file system of Windows NT, including Windows 2000, Windows XP, Windows Server 2003, Windows Server 2008, and Windows Vista in subsequent versions. FAT32 and NTFS are file systems that can be provided to storage device 100.

1 illustrates a typical storage device 100. The storage device 100 has a storage area 110 for storing various types of files (e.g., music files, video files, etc.) (some of which may be user files and others may be publisher files). Include. The storage device 100 also includes a storage controller 120 that manages the storage area 110 via data and control lines 130. The storage controller 120 also communicates with the host device 140 via the host interface 150. The host device 140 may be dedicated hardware or a general purpose computing platform.

Storage area 110 may be, for example, a NAND flash variety. Storage controller 120 may store all data to / from storage area 110, for example, by controlling “read”, “write” and “erase” operations, wear leveling, and the like and by communicating with host 140. Transfer and control all data transfers to and from the host device 140. Storage area 110 may, for example, store user files and publisher's files, protected data that is permitted to be used only by authorized host devices, and secure data that is used only internally by storage controller 120. It can be nested. Hosts (eg, host 140) do not have direct access to storage area 110. That is, for example, if the host 140 requests or requires data from the storage device 100, the host 140 must request it from the storage controller 120. In order to provide easy access to data files stored in the storage device 100, the storage device 100 is provided with a file system 160.

Storage area 110 is functionally divided into three parts: user area 170, publisher area 180, and free storage space 190. The user area 170 is a storage space in the storage area 110 in which user files are stored. The publisher area 180 is a storage space in the storage area 110 in which publisher files are stored. The free storage space 190 is an empty storage space in the storage area 110. Free storage space 190 may be used to hold user files or publisher files. When storing a user file in free storage space 190, the storage space holding the user file is subtracted from free storage space 190 and added to user area 170. Similarly, when storing a publisher file in free storage space 190, the storage space holding the publisher file is subtracted from free storage space 190 and added to publisher area 180. If a user file or publisher file is removed from storage area 110 (ie, deleted), the empty storage space is added (return) to free storage space 190.

If the size of the free storage space 190 allows this, the user of the storage device 100 may download the user file from the host 140 to the storage area 110. The downloaded user file will be stored in free storage space 190, and as described above, the storage space holding this file is subtracted from free storage space 190 and added to user area 170. As described above, the user file has priority over other (e.g., issuer) files, and in order to guarantee this priority, the desired storage use safety margin is set and, if required, recovered in the manner described below. do.

Host 140 includes storage allocator 144 to facilitate recovery of free storage space 190. Storage allocator 144 may be hardware, firmware, software, or any combination thereof. In general, storage allocator 144 determines whether the file communicated to host 140 (e.g., file 142) is a user file or a publisher file, and then displays the communicated file accordingly ( That is, as a non-disposable file or as a disposable file.

For example, if the storage allocator 144 determines that the file communicated to the host 140 (eg, the file 142) is non-disposable because the file is a user file, the storage allocator 144 Stores the file in storage area 110 in a conventional manner. As described above, the storage space in the storage area 110 that holds non-disposable files will be added to or become part of the user area 170. However, if the storage allocator 144 determines that the file communicated to the host 140 is discardable, for example because it is an issuer file, the storage allocator 144 marks the file as discardable. In some implementations, to mark a file as discardable, storage allocator 144 will recognize that the file system structure is indicated to file system 160 to indicate that the file is a discardable file. In another implementation, to mark a file as discardable, storage allocator 144 marks the file itself as discardable. If free storage space 190 is larger than the desired storage usage margin, storage allocator 144 stores the marked disposable file in free storage space 190 and maintains the disposable file, as described above. The storage space in the free storage space 190 is subtracted from the free storage space 190 (ie, the free storage space is reduced) and added to the issuer area 180 (additionally discardable file (s) 182). Logically shown).

As described above, the likelihood that issuer files may be used by a user may vary from issuer file, which makes it likely to be the first candidate for removing the least used issuer file from storage area 110. Therefore, in addition to marking a file as non-disposable or discardable, the storage allocator 144 may store each discardable file before, concurrently with, or after the discardable file is stored in the storage area 110. Assign revocation priority levels.

By marking a file as non-deletable or discardable, assigning a discard priority level by storage allocator 144, and using file system 160 (or an image thereof) of storage device 100, the storage allocator ( 144 “knows” the number of user files and publisher files in storage area 110, and their sizes and logical locations in storage area 110. Knowing this information (i.e. number, size, and location of the files), and in particular based on one or more of the indicated files, storage allocator 144 may be adapted to the storage area 110 and the files requested by the storage area 110; Manage storage of unsolicited files. Managing the storage area 110, or managing the storage of files in the storage area 110 may recover the storage use safety margin, for example by selectively removing one or more files marked as discardable and discardable. It may include emptying the storage area by removing all files marked with, and remapping files of multiple clusters to low-performance storage modules. Managing the storage area 110 or files stored therein may include managing other, additional, or alternative aspects of the storage area 110 or files stored therein.

In addition, the storage allocator 144, by means of the discard level assigned to each discardable file, recovers the free storage space originally reserved for the user file in the future (i.e., saves the desired storage usage safety margin). To recover) the order in which discardable files can be discarded or to be discarded (ie, deleted or removed from storage area 110) is known. Thus, if a user wants to store a new user file in storage area 110 but does not have enough free storage space to accommodate this user file (this means that the storage usage margin is narrower than desired), storage allocation. 144 recovers more free storage space by repeatedly deleting the discardable files in sequence using the discard priority levels assigned to the discardable file until the desired storage use safety margin is recovered to the maximum (ie, , Increase free storage space 190). As described above, the maximum recovered storage use safety margin guarantees a high probability that sufficient free storage space will be reserved for future user files. It is contemplated that a user may want to use a stored disposable file occasionally, so that the storage space to accommodate this file is removed from the storage device only if it is required for the new user file, so the discardable file can It is removed or deleted from the storage device 100 only in response to receiving a request to save. Storage allocator 144 may be embedded or included within host 140, or may be external to host 140 and storage device 100 (shown as dashed box 144 ′).

Storage allocator 144 has a typical image of a file system of or associated with storage device 100. Storage allocator 144 uses the file system image of the storage device to mark a file as non-desirable or discardable and to assign a discard level to each discardable file. In one example, the file system includes a FAT, in which case the marking is done to the unused portion of the FAT entry associated with the file by setting one or more unused bits. Since different file systems have different structures, marking a file (ie, as non-disposable or discardable) and assigning discard levels are as described above in FIGS. 6-1 and described below in connection with them. Likewise, it is modified to match the file system structure used.

2 is a block diagram of a portable storage device 200 according to another embodiment. Storage controller 220 functions like storage controller 120 and storage allocator 244 functions like storage allocator 144. Storage allocator 244 can be hardware, firmware, software, or any combination thereof. Storage allocator 244 internally cooperates with storage controller 220. The request includes an indication of whether the file is a discardable file, and whenever the storage controller 220 receives a save request from the host 240 to store the file in the storage area 210, the storage controller 220. Notifies storage allocator 244 whether the storage request and the file are discardable. Storage allocator 244 then marks the file as non-destroyable or discardable in the structure of the file system associated with storage device 200. Typically, applications running on host 240 determine that the file is a discardable file and send a flag or other indication to storage controller 220 indicating that the file is a discardable file. Applications running on host 240 send a flag or other indication as part of the storage protocols to request storage of the file to the storage device. Examples of such storage protocols include the use of POSIX file system functions or the java.io class tree.

If storage allocator 244 determines that the new file is discardable, storage allocator 244 assigns a discarding priority level to the new file according to the usage probability of the file. Storage allocator 244 then evaluates the current size of free storage space 290 and determines whether one or more discardable files should be removed (ie, deleted) from storage area 210 to make room for new files. do. If the discardable file or files are to be removed from the storage device, storage allocator 244 determines which file (s) is the current candidate file for removal. Storage allocator 244 then notifies storage controller 220 of the discardable file to be removed from storage area 210, and in response, storage controller 220 is directed by storage allocator 244. Remove discardable files or files. In some configurations of portable storage device 200, storage allocator 244 can be functionally disposed between storage controller 220 and storage area 210. In configurations where storage allocator 244 is functionally disposed between storage controller 220 and storage region 210, storage allocator 244 or storage region 210 may be one of the functions of storage controller 220. You have to take some. In such configurations the storage area 210 is comprised of memory units communicating at a higher level than flash NAND protocols.

3 is a block diagram of a storage allocator 300 according to an embodiment. Storage allocator 300 includes a memory unit 310, a processor 320, and an interface 330. The memory unit 310 may maintain a file system structure or an image of the file system structure, associated with the storage device (eg, the storage device 200 of FIG. 2). Processor 320 manages file systems associated with storage devices. The interface 330 may be configured to cooperate with the host and with the storage controller of the storage device as shown in FIG. 1, or only with the storage controller of the storage device as shown in FIG. 2.

The processor 320 receives via the interface 330 a request to store a file in a storage area of the storage device and discards the file in a structure of a file system associated with the storage device on which the storage allocator 300 operates. It is configured to be marked non-disposable. If interface 330 is functionally attached to storage controller 220 of FIG. 2 (thus receiving, for example, SCSI or wrapped USB / MSC commands rather than file level commands), the received request is It is at a much lower level than the file level. That is, the received request would be a request to store a sector at logical block addresses that would correspond to a file when correctly interpreted by the host. If the storage controller 220 supports the NVMHCI protocol, or a networking file system protocol such as NFS, or a similar protocol, the storage controller 220 can obtain file level requests. Therefore, communication between a storage controller such as storage controller 220 and an interface such as interface 330 is not limited to NVMHCI or to NVMHCI-like implementations. The communication interface 330 may be integrated into the storage allocator 300, as shown in FIG. 3.

The processor 320 is further configured to send the indicated file to the storage device, and marking the file as discardable includes assigning the file to a discard priority level. If the file system used by the storage device is FAT-based, the processor 320 sets the discard priority level by setting a value corresponding to the m most significant bits (e.g., m = 4) to the FAT corresponding to the indicated file. Is assigned to the indicated file. The corresponding value set in the most significant bit in the FAT entry, or the value set in the NTFS directory entry, may be or may be an attribute of the file. By "attribute" is meant any data structure or metadata tag in the header of a FAT table or NTFS table that contains information pertaining to the type of content stored in the table. "Advertisement", "Premium content", and "Promote (free) content" are representative types of content that can be stored in a FAT table or in an NTFS table. Alternative criteria for setting revocation levels are, for example, last accessed file, file size, file type, and the like.

The number m of most significant bits of a FAT32 entry used only to mark a file may be less than 4 or 4 since these bits are not used. Also, the more bits used, the more discarding priority levels may be used. For example, using three bits (i.e. m = 3) gives eight (2 ³ = 8) discarding priority levels and using four bits (i.e. m = 4) 16 Provide a discarding priority level of (2 ⁴ = 16) (ie, including a discarding priority level of "0" assigned to the non-deletable file). That is, the processor 320 sets the value of m most significant bits to 0 if the displayed file is not discardable or to a value between 1 and 2 ^m -1 if the displayed file is discardable. The discard priority level indicates the priority at which the indicated file can or should be discarded from the storage device. For example, depending on the implementation, the value "1" may indicate a file that is discardable at the lowest priority or discarded at the highest priority, and the value "2 ^m -1" may be discardable or lowest at the highest priority, respectively. Priorities can indicate files that can be discarded.

The processor 320 may assign revocation priority levels to the indicated file according to the expected use of the file, as described above with respect to the likelihood or probability that an unsolicited file will be used by the user of the storage device. The processor 320 may update the discarding priority level of the displayed file in response to, or in response to receiving, each request to store a new file on the storage device. Processor 320 may update the discarding priority level of a given indicated file independently from one or more new requests to save the file to storage. For example, a file that previously had high priority may have a lower priority after some time interval. Processor 320 deletes the file stored in the storage device if the file is associated with a discard priority level equal to or greater than a predetermined discard threshold. The processor 320 may (re) set the discard threshold based on file records or additions, or depending on the expected use of free storage space on the storage device or the availability of a new publisher file.

The memory unit 310 may maintain an allocation table 340 containing discarding priority levels that the processor 320 assigns to files stored in the storage device. In addition, the allocation table 340 may maintain identifiers and information of the file that associates the file with revocation priority levels assigned to them. In addition, the allocation table 340 may maintain a discard threshold. The information maintained in the allocation table 340 allows the processor 320 to identify which discardable files or files can be removed from the storage device to restore the desired storage use safety margin.

In response to receiving the request to store the new file on the storage device, the processor 320 evaluates the size of the free storage space f on the storage device, and the estimated size of the free storage space on the storage device is a predetermined size. If greater, store a new file on the storage device, or if it is not larger than a predetermined size, the processor 320 searches for one or more discardable files in the storage device that can be deleted, and when such a file or file is found, the processor 320 deletes this file or files to expand the current free storage space f so that the total size of the expanded free storage space is equal to or greater than the predetermined size. A discardable file or file is deleted from the storage device if the discard priority level associated with the discardable file is equal to or greater than a predetermined discard threshold (eg, between 1 and 15, including, for example, 15). Can be.

After the free storage space is fully expanded, the processor 320 causes the new file to be stored in the expanded free storage space. Expanded enough "free storage space" means that total free storage space can accommodate new files, or equivalently, until the total free storage space can accommodate new files without narrowing the desired storage usage margin mentioned above. By freeing the occupied storage space in turn, until the size is equal to or larger than the predetermined size, or until all discardable files are removed, it is meant to expand the free storage space.

Processor 320 may be a standard off-the-shelf system-on-chip (“SoC”) device or a system-in-package (“SiP”) device, or when executed, performs the steps, operations, and evaluations described herein. It may be a general purpose processing unit having dedicated software. In the alternative, the processor 320 may be an application specific integrated circuit (“ASIC”) that implements the steps, operations, and evaluations described herein by using hardware.

Fig. 4 is a method of storing a discardable file according to an exemplary embodiment. 4 will be described with reference to FIG. 1. In operation 410, the host 140 receives a request to store the file 142 in the storage device 100. In step 420, storage allocator 144 marks the file as " disposable " or " non-disposable ", and if the free storage space 190 is large enough in step 430, the storage device 100 To storage controller 120 (ie, for storage in storage area 110). The file is also indicated in terms of the discard priority level assigned to the file. In step 440, storage allocator 144 is based on the displayed file, optionally based on one or more files already displayed, storage area 110 (via communication with storage controller 120) or storage area. Manage files stored in 110.

5 is a method of managing the storage of discardable files on a storage device according to one exemplary embodiment. FIG. 5 will be described with respect to FIG. 1. The new file is a candidate for storage in the storage device 100. Since the current image of the file system 160 of the storage device 100 is known, the storage allocator 144, at step 510, free storage space 190 whose current size is f is a new file (i.e. , The current size " f " of the free storage space 190 is evaluated to see if it can accommodate a file that is a candidate for storage. In general, how storage allocator 144 handles new files depends on whether the new file is a user file or a publisher file. Therefore, storage allocator 144 first determines whether the new file is a user file or a publisher file.

New file custom file

At step 520, storage allocator 144 checks whether free storage space 190 can accommodate the new user file. If free storage space 190 can accommodate the new user file (indicated as "Y" in step 520), storage allocator 144 stores the desired storage by storing the new user file in step 560. The new user file is stored in the free storage space 190 regardless of whether the safety margin for use is narrowed. After the storage allocator 144 stores the new user file in the free storage space 190 and the desired storage usage safety margin narrows (ie, with respect to the desired storage usage safety margin), the storage allocator 144 Does not take any further action with respect to the storage of the new user file.

However, after the storage allocator 144 stores the new user file in the free storage space 190 and the desired storage usage safety margin narrows, step 550 may be performed to maintain the desired storage usage safety margin. The storage allocator 144 further includes determining which stored discardable files are to be deleted first and which stored discardable files are to be deleted second. The storage allocator 144 is based on the discarding levels assigned by the storage allocator 144 to the stored disposable files, such that any stored disposable files are deleted first, which stored disposable files are deleted second, and so on. Determine.

If storage allocator 144 determines that free storage space 190 cannot accommodate the new user file (provided as " N " in step 520), storage allocator 144 is assigned to the discardable file. It is determined in step 530 whether the free storage space 190 and the storage space consumed by it are sufficient to store a new user file when combined. If there is not enough combined storage (shown as "N" in step 530), this means that no matter how many discardables are deleted, the new user file cannot be stored in the "non-user" storage area because it is larger. Means. If the combined storage space is sufficient (shown as "Y" in step 530), storage allocator 144, at step 540, discards the stored discard to leave enough storage space for the new user file. Search for which discardable files of the possible files can be deleted. As described above, storage allocator 144 marks files as non-disposable or discardable in the file system of the storage device, so that storage allocator 144 uses them by using the file system of storage device 100. Search for discardable files. Furthermore, revocation levels assigned to a file indicated by storage allocator 144 are embedded in the file system of the storage device such that each revocation level is associated with a corresponding indicated file.

When you first find a disposable file ("DF") to discard (this file is referred to as "DF1" below), storage allocator 144 stores the storage space (this storage space is referred to as "SP1" below). The file DF1 is deleted to add to the space 190 or to recover it.

Then, at step 550, storage allocator 144 may have expanded free storage space 190 (i.e., free storage space 190 + last reclaimed storage space, or f + SP1) to accommodate the new user file. Check if you can. If the extended free storage space 190 (ie, f + SP1) still cannot accommodate the new user file (denoted as "N" in step 550), the storage allocator 144 allocates additional storage space. To recover to free storage space 190 (ie, by finding and deleting the next discardable file to delete), step 550 is repeated (repeats are shown at 555).

When the next discardable file with the second highest discarding priority is found (the next discardable file is referred to below as "DF2"), the storage allocator 144 adds additional storage space (additional storage space referred to as "SP2"). File DF2 is deleted to free it and add it to the free storage space 190. Subsequently, at step 550, storage allocator 144 has expanded free storage space 190 (i.e. free storage space 190 + two last freed storage spaces, or f + SP1 + SP2). Check again if it can accept If the extended free storage space 190 (ie, f + SP1 + SP2) still cannot accommodate the new file (indicated as "N" in step 540), storage allocator 144 may discard and then discard it. Repeat step 540 one or more times to find the file. Storage allocator 144 repeats steps 540 and 550 until the accumulated free storage space 190 can accommodate the new user file (indicated as " Y " in step 550). Next, at step 560, storage allocator 144 stores the new user file in storage area 110.

As mentioned above, if the storage allocator 144 stores the new user file in the free storage space 190 and the actual storage use safety margin becomes narrower than the desired storage use safety margin, step 560 is desired. The storage allocator 144 may include an additional step of determining which stored discardable files are deleted first, which stored discardable files are deleted second, and so on in order to recover the storage usage safety margin.

New file publisher file

If the new file is a publisher file, storage allocator 144 stores the new publisher file only if free storage space 190 can accommodate the new publisher file without narrowing the desired storage usage margin. Save at 110 (at step 560). In other words, if storing a new publisher file results in narrowing the desired storage usage margin, storage allocator 144 may decide not to store the new publisher file in storage area 110. In this case, storage allocator 144 stops taking any action on this file and does not delete any files from the storage device to free storage space for the new publisher file. Alternatively, storage allocator 144 may delete one or more high priority discardable files in step 540 to free storage space for discardable files with low discard priority. As mentioned above, the file is displayed, the revocation levels are inserted into the file system of the storage device 100, the files are displayed, and the revocation levels are inserted into the file system depending on the file system used, or Can be modified to suit.

Fig. 6 is a method of displaying a file not required for a FAT32-structured file system, according to one exemplary embodiment. FAT32-structured file systems use clusters. As described above in connection with FAT32-structured file systems, the number of bits used to identify the FAT32 cluster is 32. FIG. 6 will be described with reference to FIG. 1.

In step 610, the 32-bit m (m < 4) most significant bits of each cluster of FAT32 correspond to the file as non-destructible or discardable, as appropriate, and for each discardable file. Is allocated to or maintained for maintaining the discard level. Assigning a discard level to a file is done by setting the corresponding value to the assigned m bits corresponding to the displayed file.

In step 620, storage allocator 144 assesses the level of likelihood of using a file that has not been requested by a user of storage device 100. The assessment of the likelihood of using the file may be implemented in various ways known to those skilled in the art in the description of the consignment file. For example, the assessment of the likelihood of using the file may be based on monitoring the location of the person using the storage device and / or based on previous experiences and preferences of the monitored user. The assessment of the likelihood of using a file may be based on, for example, the type of content stored in the FAT table or the NTFS table (eg, “advertisement content”, “premium content”, “publicity (free) content”, etc.). . Storage allocator 144 may use alternative or additional criteria to assess the likelihood that a file will be used. For example, attributes or features of the file (s) may be used, which may be or associated with the last accessed file (s), file size, file type, and the like.

After storage allocator 144 evaluates the level of likelihood of using a file that the user did not request, storage allocator 144, at step 630, corresponds to the estimated likelihood level of use of the unsolicited file. Assigns a discarding priority level. The higher the likelihood that an unsolicited file will be used by the user of storage device 100, the lower the discard level.

If m is equal to 4 bits, this means providing 15 discard levels with a discard scale of 1 (ie 0001) to 15 (ie 1111). That is, discard level 0 will be assigned to all non-destructible files, discard level 1 will be assigned to discardable files with the lowest discard priority, and discard level 15 will be assigned to discardable files with the highest discard priority. . After storage allocator 144 assigns a file that does not require a corresponding discard level, storage allocator 144, in step 640, is associated with a file that did not require a corresponding value between 1 and 15. Set to the four most significant bits of the cluster. If an unsolicited file associates it with two or more clusters, the four most significant bits in each cluster are set to the same value.

In step 650, it is checked whether the unsolicited file is the last file that needs to be evaluated. If the unsolicited file is not the last file that needs to be evaluated (indicated as "N" in step 650), another file is evaluated in the manner described above. If the unsolicited file is the last file that needs to be evaluated (indicated as "Y" in step 650), the unsolicited file (s) each have an m bit whose value has been set in step 640. Are sent to the storage device.

7 is a directory table 700 associated with a FAT32 table. Directory table 700 is only a partial table used for illustration, so table 700 does not show all the fields of a FAT directory entry. Directory area 700 maintains details of files that are stored in the associated file system, such as file names, file sizes, and where each file begins in the associated file system. The details of the file are kept in the following fields. Field 710 holds the disk operating system ("DOS") file names of the file stored in the file system concerned, field 720 holds the file's extension, field 730 holds the various attributes of the file, Field 740 holds the high 16-bitword of the first cluster number ("FCN") of the file, field 750 holds the lower portion of the first cluster number ("FCN") of the file, and the field 760 maintains the size of the file. Each FCN number represents a first logical cluster where a file can be found.

The first entry of directory area 700 holds information about a file called "REALFILE" (denoted 770). REALFILE 770 has a file extension "DAT" whose FCN is "0000 0002" (denoted by 755) and its size is "0000 24E4". In table 700, numbers are represented as hexadecimal values. As part of the standard, attribute values "00" (indicated by 780) and "20" (not shown in FIG. 7) refer to "normal" files, and attribute value "02" refers to files hidden in the file system. do. The file name "\ xE5Consign" indicates a deleted file, and "\ xE5" means that the value of the first byte of the file name is hex and E5. As an example, the FCN number 0000 0002 (denoted 755) refers to the first cluster of the file REALFILE.

8 is a partial FAT32 table 800 according to an embodiment. FAT32 table 800 is shown as a double-word ("DWORD") array, where the values are hexadecimal values. Reference numeral 810 denotes the type of device that holds the FAT32 table 800, and "F8" refers to the hard drive. FAT32 table 800 includes 23 clusters referred to as cluster # 1 (shown 820), cluster # 2 (shown 825), ..., and cluster # 23 (shown 830). FIG. 8 is described with reference to FIG. 7. The cluster in FAT32 table 800 may be the first cluster of files, or may point to the next linked cluster of files, or may be an end-of-file (“EOF”) representation.

Referring back to directory area 700, the first FCN (indicated by 770) of directory area 700 is " 0000 0002 " (indicated by 755), which indicates cluster # 2 in table 800 of FIG. . As shown in Figure 8, the value of cluster # 2 (i.e., the value "000 0003") points to cluster # 3, which is the cluster of the next file (indicated by 840). Similarly, the value of cluster # 3 (ie, "0000 0004") points to cluster # 4, which is the cluster of the following files. Cluster # 4 has the value "OFFF FFFF" ("F" is a hexadecimal digit representing the decimal value "15"), and "FFF FFFF" (denoted 850) represents the EOF representation of the file, and a zero value (860). Denotes a discard level 0. Therefore, the file REALFILE associates it with three clusters (ie cluster # 2, cluster # 3, cluster # 4).

As described above, discard level 0 is assigned to a non-cancelable file. Note that the highest hexadecimal digit of each cluster of a particular file is set to the same discarding priority level assigned to this file. For example, file REALFILE has been assigned revocation level "0", so each of the most significant hexadecimal digits of clusters # 2, # 3, and # 4 have this value (ie, values "0", and "). 0 "values are underlined). According to another example, file "E5 Consign" with FCN "0000 0005" (as shown in Figure 7) has been assigned a revocation priority level "1". Therefore, the most significant hexadecimal digit of each of clusters # 5-12 belonging to this file has the value "1" (eg, as indicated by 870). That is, as disclosed herein, the most significant hexadecimal digit, or equivalently, the four most significant bits of the cluster associated with a particular discardable file are set to the same value corresponding to the discard priority level assigned to the particular file. As described above, the number m of most significant bits used to indicate the discard priority level may not be four (ie, m ≦ 4).

9 is a partial NTFS table 900 according to an embodiment. NTFS table 900 maintains details of files such as file names, file sizes, and the like. NTFS table 900 includes data fields 910 to hold "normal" data (e.g., data 920) for files that change in accordance with "normal" data flow. As disclosed herein, NTFS table 900 includes a "Discard Information" field 915 for holding revocation information (e.g., revocation information 930) for each evaluated file. The revocation information field 915 may also include information other than the revocation priority level. For example, the discard information field 915 may include information pertaining to the server that supplied the file and the expiration time (the file should be discarded afterwards). Unlike FAT-based file systems, in NTFS-based file systems, discard values assigned to discardable files are not limited to the maximum number indicated by a set of bits. This means that the range of discard values can be chosen freely. For example, the discard values may range from 1 to 25. NTFS is a representative non-FAT file system. In general, corresponding discard values may be set in the data field in non-FAT based file system entries corresponding to the indicated file.

10 is a logical arrangement of a file system 1000 of a storage device according to an embodiment. The storage allocator (eg, storage allocator 144 of FIG. 1) maintains an image of the file system 1000 or file system 1000 of the storage device on which it operates, or the storage allocator is a file system 1000. You can also access

File system 1000 includes a boot section 1010, a FAT 1020 associated with file system 1000, directory tables 1030, files area 1040, and discardable files area 1050. . FAT 1020 includes a discardable files allocation area 1025 that contains discard priority levels of discardable files. The directory table 1030 includes access information for accessing what files (ie, discardable files and / or non-discardable files) are stored on the storage device. File area 1040 contains a non-discardable file. Index and database area 1045 maintains metadata related to indexes and discardable files for discardable files. Indexes and metadata maintained in the index and database area 1045 are used to calculate the discard level but they are not required during the actual discard process. Discardable file area 1050 holds a discardable file.

11 illustrates a file management method according to the present disclosure. FIG. 11 will be described with respect to FIG. 1. Assume that two user files (ie, files "F1" and "F2") are initially stored in storage area 110 at time T0. Since the files " F1 " and " F2 " are user files, they are stored in the user area 170, and the discard level assigned to them by the storage allocator 144 is zero. Since the total storage capacity of the storage area 110 is T (indicated by 1110) and the files F1 and F2 are stored in the storage device 100, the size of the remaining free storage space 190 (see FIG. 1) is f (indicated by 1120). Assume that the publisher wants to store three unsolicited files in storage area 110. As described above, storage allocator 144 stores the desired unused storage safety margin 1130 in which storage of the publisher's three unsolicited files in storage area 110 is reserved for future users' files. To determine whether to narrow the), the size of the free storage space 190 (or 1120 f) in the storage device 100 is evaluated. If storing the publisher's three unsolicited files would narrow the storage use safety margin 1130 (ie, the desired storage use margin), storage allocator 144 stops storing these files. Will be placed.

In this example, storage allocator 144 determines that the publisher's three unsolicited files can be stored in storage area 110 without reducing storage usage safety margin 1130. Therefore, at time T1 storage allocator 144 causes storage controller 120 to store the three unsolicited files of the publisher in storage area 110. Unsolicited files from three publishers have been labeled "P1", "P2", and "P3". The storage allocator 144 also determines the probability that the files P1, P2, P3 will be used by the user of the storage device 100 and assigns a corresponding discard level to each of these files. Storage allocator 144 then stores the discard levels assigned to the file in a FAT table, as shown in FIG. 8, or in an NTFS table, as shown in FIG. 9.

At time T2, the user of storage device 100 wants to store two or more files (ie, files "F3" and "F4") in storage area 110. Storage allocator 144 is free storage space 190 in storage device 100 to determine if there is sufficient storage space in storage area 110 to store additional files (ie, files F3 and F4). Re-evaluate the size (or f at 1120). In this example, storage allocator 144 determines that the current free storage space can accommodate files F3 and F4. Therefore, at time T2, storage allocator 144 enables storage controller 120 to store files F3 and F4 in storage area 110.

Since files F3 and F4 are user files, the probability that files F3 and F4 will be used by the user of storage device 100 is how many, even if the user uses files F3 and F4. This is irrelevant because user files have storage priority over publisher files, regardless of how many times they are used. Thus, storage allocator 144 assigns discard level " 0 " to files F3 and F4, and assigns the assigned discard level to a FAT table as shown in FIG. 8, or as shown in FIG. Store in an NTFS table.

At time T3, the user of storage device 100 wants to store another file (ie, file “F5”) in storage area 110. Storage allocator 144 is configured to determine whether there is sufficient storage space in storage area 110 to store additional files (i.e., files F5). Reevaluate size (or f at 1120).

In this example, storage allocator 144 determines that the current free storage space can accommodate file F5. Therefore, at time T3, storage allocator 144 enables storage controller 120 to store file F5 in storage area 110. As shown in Fig. 11, storing the user file F5 narrows the storage use safety margin. That is, the free storage space f in the storage area 110 remaining after the files F1 to F5 and P1 to P3 are stored in the storage area 110 is smaller than the storage use safety margin 1130. Therefore, storage allocator 144 restores or recovers a storage usage safety margin by removing one of the publisher's files (ie, P1, P2, P3). As described above, because the user files have the highest storage priority, the storage use safety margin is restored or recovered by removing (ie, deleting) one or more publisher files.

As described above, the determination that the issuer file or issuer files will be removed from the storage area 110 is determined by the storage allocator 144 based on the discard priority level assigned by the storage allocator 144 to each stored discardable file. ) Is performed.

Returning to FIG. 11 again, it is assumed that among the stored publisher files P1 to P3, the publisher file P3 has been assigned the highest revocation priority level (eg, 13). Therefore, at time T4, file P3 is removed from storage area 110, thereby making free storage space 190 large. Since the size of the free storage space 190 (or f at 1120) at time T4 is larger than the storage usage safety margin 1130, no further publisher files need to be removed.

A user of storage device 100 may wish to remove one or more user files. At time T5, the user removed two of his files (i.e., files F4 and F5), thus freeing up storage space 190 larger. As mentioned herein, restoring free storage space or restoring storage usage safety margins is done by removing as many disposable files as necessary, so that removal of files F4 and F5 is free storage space 190. Or the size of the storage use safety margin. Assume that the publisher wants to store another unsolicited file in storage area 110. As described above, storage allocator 144 uses free storage space to determine whether storing unsolicited files of issuers in storage area 110 will narrow storage use safety margin 1130. Evaluate the size of 190 (or f at 1120). If saving the publisher's new unsolicited file would narrow the storage usage safety margin 1130, storage allocator 144 would stop saving this file.

In this example, storage allocator 144 determines that the publisher's new unsolicited file (ie, file "P4") can be stored in storage area 110 without reducing storage usage safety margin 1130. do. Therefore, at time T6, storage allocator 144 causes storage controller 120 to store the publisher's file P4 in storage area 110. The storage allocator 144 also determines the probability that the file P4 will be used by the user of the storage device 100 and assigns a corresponding discard level to this file. The storage allocator 144 then stores the discard level assigned to the file P4 in the FAT table as shown in FIG. 8 or in the NTFS table as shown in FIG. The process of storing new publisher's files and new user files and removing stored files means that the storage allocator 144 has a current size of the free storage space 190 each time a new file needs to be added to the storage area 110. Can be continued while evaluating and determining which publisher file or files (if any) from storage area 110 should be removed.

Assigning a discard level to a discardable file may be based on user experience or preferences, may be based on the user's Global Positioning System (GPS) location, and / or may be based on other criteria. For example, if a user of the storage device seems to like some type of music (based on previous user experience), the storage allocator will issue the publisher if the publisher's file contains music that is one of the user's favorite types of music. It is possible to assign a relatively low discard priority level (e.g., 3 on a scale of 1 to 15) to a file. However, if the user does not like the publisher's music (based on previous user experience), the storage allocator may assign a higher discard priority level (e.g., 12 on a scale of 1 to 15) to the file of the publisher concerned. have. The criteria used to assign the discard level to a discardable file include the expected use of the file, the estimated revenue associated with using the file, the type of file, the size of the file, the location of the file within the storage device, the storage period of the file, and Other criteria or parameters as specified herein may be included. Other criteria, either alone or in combination with any of the criteria mentioned herein, can likewise be used, and the assignment of revocation levels can be done using one or more criteria. In addition, different criteria may be used to assign discard levels to different discardable files.

In another example, if a publisher wants to send a location-dependent advertisement to a user (ie, an advertisement related to a product or service demonstrated within a particular region), the storage allocator assigns a discard priority level to the publisher's advertisement that varies with the user's changing location. Can be assigned. That is, deviating from a particular area may assume that the user is not interested in consuming a product or service demonstrated in a particular area, so the further the user is away from a particular location, the higher the disposal level will be.

As described above, cluster chains for discardable files are written to the FAT with a flag identifying the file associated with the FAT32 entry as a discardable file. Typically, the flag is in the four most significant bits in each FAT32 entry. Because cluster chains can be assigned to discardable files but do not have any non-disabled files associated with them, utilities such as chkdsk or fsck.vfat replace the discardable files with non-disposable files, also known as "real" files, so that the file system It is possible to reduce the security of 160. Also, there is a risk that some FAT recovery utilities will reset the discardable-file flags on FAT32 entries. FAT32 file system check and repair utilities often apply file systems and apply rules to correct common errors. In general, these utilities can find cluster chains in the FAT that do not have an entry corresponding to the first cluster number (FCN) field in the directory tables. Utilities treat cluster assignments as FAT data fragments (also known as orphan clusters) in a FAT that does not have any directory or file entries, and the utilities delete these orphan clusters or correspond to directory tables. You can create a file entry. Because the disposable file system described herein may utilize what might have been considered an orphaned cluster, utilities may inappropriately replace a disposable file with a non-disposable file or completely remove the disposable file.

To solve these problems, in some implementations, storage allocator 144 may associate a discardable file with a cluster chain in the primary FAT, which hides the physical location of the discardable file, 144 stores the physical location of the file in a disposable FAT, database, or one or more location files. Typically, a primary FAT is unknown to a discardable FAT, database, or one or more location files, and in some implementations, a discardable FAT that prevents the host operating system from accessing the discardable FAT, database, or one or more location files; Attributes associated with a database or one or more location files may be activated.

As mentioned earlier, each entry in FAT32 is 32 bits, but only the lower 28 bits are used. Typically, the top four bits are reserved and set to zero. Implementing FAT32 requires that the upper four bits be set to zero when writing a new FAT entry, ignoring the upper four bits if set in the allocated clusters. A discardable file is distinguished from a non-destructible file by a flag in the top four bits of the FAT entries of each cluster chain associated with the file. Standard FAT32 drivers will consider discardable files as allocated space and will not overwrite them. However, storage allocator 144 may periodically perform operations such as those described above with respect to FIG. 5 to maintain free space allocations in storage device 110, and allocate space allocated to discardable files. Can be recovered.

By using at least one of the discardable FAT, the database, and one or more location files and the primary FAT, the primary FAT can be expanded. One or more location files that reflect the physical location of a discardable FAT, database, or discardable file when the primary extended FAT is used in conjunction with a branch in the file allocation table lookup logic so that the top four bits of the FAT entry are not zero. Use the information in the main FAT instead of the FAT entry. Due to information in a discardable FAT, database, or one or more location files that ignore values in the FAT entry of the primary FAT, utilities such as chkdsk and fsck.vfat allow utilities to discard clusters of discardable files. It will not replace a discardable file with a non-discardable file because one or more location files will be considered as associated with directory or file entries. In addition, FAT recovery utilities consider utilities such as chkdsk and fsck.vfat to regard a cluster associated with a disposable file as not associated with the free space, but with a directory or file entries in the disposable FAT, database, or one or more location files. It will not reset flags to FAT32 entries indicating that the file is a discardable file.

When file system 160 uses primary FAT 1200 and discardable FAT 1201 to store a file marked as discardable, storage allocator 144 is assigned a cluster chain 1202 assigned to the discardable file. Update primary FAT 1200 as shown in FIG. 12A to associate it with the file. In general, cluster chain 1202 may be the same size or larger than the discardable files associated with cluster chain 1202. In some implementations, cluster chain 1202 masks the physical location of discardable files in the primary FAT. Typically, as described above with respect to FIGS. 7 and 8, each cluster in the cluster chain starting at entry 1204 has a value equal to 1FFF FFFF as shown in entry 1206. Point to the next sequential cluster of cluster chain 1202 until the end. However, in other implementations, each cluster of the cluster chain may have a value such as 1FFF FFFF indicating that the cluster is an individually allocated cluster rather than pointing to the next sequential cluster of the cluster chain.

The first entry 1204 of the cluster chain 1202 points to the corresponding entry 1208 in the discardable FAT 1201, as shown in FIG. 12B. As described above with respect to FIGS. 7 and 8, for each file, each cluster in the cluster chain 1202 in the discardable FAT 1201 has a value such as 1FFF FFFF as shown in entry 1210. Point to the next sequential cluster of files until this file's EOF is indicated.

It will be appreciated that one cluster chain 1202 may be associated with one or more files. For example, as shown in FIG. 12B, the cluster chain 1202 is the first set of clusters # 6 (element 1208) to cluster # 9 (element 1210) for the first file 1212. Cluster, the second set of clusters being cluster # 10 to cluster # 11 for the second file 1214.

It will also be appreciated that primary FAT 1200 and corresponding discardable FAT 1201 may include one or more cluster chains. For example, as shown in FIGS. 12A and 12B, the primary FAT may include cluster chain 1202 of clusters # 6 to # 11, and the second cluster chain of clusters # 20 to cluster # 22 ( 1216).

In another implementation, rather than using primary FAT 1200 and discardable FAT 1201, the file system may use primary FAT 1200 to associate one or more files to a cluster chain, as described above, A database or one or more separate location files may be used in place of the discardable FAT to store the physical locations of one or more discardable files associated with the cluster chain. The database or location file may be text files or binary files stored in a non-disposable area of the file system.

13 is a method of managing a storage device using a primary FAT and a disposable FAT. FIG. 13 will be described with reference to FIG. 1. In operation 1310, the host 140 receives a request to store the file 142 in the storage device 100. In some implementations, storage allocator 144 derives a request to store file 142 in storage device 100 based on one or more write requests associated with the file.

At step 1320, storage allocator 144 marks the file as " disposable " or " non-disposable " in the file system structure associated with storage device 100 as described above. In step 1320, the file is also indicated that a discard priority level is assigned to the file.

In step 1330, when the file is a discardable file, storage allocator 144 updates the primary FAT to associate the cluster chain assigned to the file with this file. In step 1340, storage allocator 144 updates the discardable FAT to reflect the physical location of the file on storage device 100. In step 1350, storage allocator 144 manages storage area 110 of storage device 100, and stores files stored in storage area 110 (via communication with storage controller 120). Manage based on the displayed files and in accordance with the disposable FAT. Management of the storage area is similar to that described above with respect to FIG.

14 is a method of managing a storage device using a FAT and a database. FIG. 14 will be described with reference to FIG. 1. In operation 1410, the host 140 receives a request to store the file 142 in the storage device 100. At step 1420, storage allocator 144 marks the file as " disposable " or " non-disposable " in the file system structure associated with storage device 100 as described above. In step 1420, the file is also indicated that a discard priority level is assigned to the file.

In step 1430, when the file is a discardable file, storage allocator 144 updates the FAT to associate the cluster chain assigned to the file with this file. In step 1440, storage allocator 144 updates the database to reflect the physical location of the file on storage device 100. At step 1450, storage allocator 144 manages storage area 110 of storage device 100 (via communication with storage controller 120), or stores files stored in storage area 110 as FAT. And based on a database.

15 is a method of managing a storage device using a FAT and a location file. FIG. 15 will be described with reference to FIG. 1. In operation 1510, the host 140 receives a request to store the file 142 in the storage device 100. At step 1520, storage allocator 144 marks the file as " disposable " or " non-disposable " in the file system structure associated with storage device 100 as described above. In step 1520, the file is also indicated that a discard priority level is assigned to the file.

In step 1530, when the file is a discardable file, storage allocator 144 updates the FAT to associate the cluster chain assigned to the file with this file. At step 1540, storage allocator 144 updates the location file to reflect the physical location of the file on storage device 100. In step 1550, storage allocator 144 manages storage area 110 of storage device 100 (via communication with storage controller 120), or FAT stores files stored in storage area 110. And based on the location file.

In another implementation, storage allocator 144 may be used to enhance security and to prevent file system destruction or corruption by file system integrity utilities such as dosfsck (also known as fsck.vfat) or chkdsk. To ensure that cluster chains cannot be rebuilt without reading one or more location files that store the physical location of the discardable FAT, the database, or the discardable file, the cluster chains sequentially into the discardable file area. Do not assign to In addition, the scope associated with one or more of the scrambled clusters in the cluster chain such that utilities such as dosfsck do not convert a discardable file to a non-discardable file or do not reset the flag on the higher bits of the file indicating that the file is discardable. The files are created in the FAT. In some implementations, attributes such as concealment, system, directory, or volume attributes associated with a scope file can be activated to prevent the host operating system from accessing the scope file.

FIG. 16 is a chart illustrating a FAT including a cluster chain in which an order of two or more clusters including a cluster chain is scrambled. As shown in FIG. 16, clusters comprising a cluster chain starting at entry 1602 are not contiguous. For example, the order of cluster chains starting at entry 1602 is cluster # 13, cluster # 9, cluster # 7, cluster # 18, and cluster # 21. In the FAT, the value of each cluster points to the next cluster in the cluster chain as described above in relation to FIGS. 7 and 8.

In addition to scrambling the order of clusters that include cluster chains associated with one or more files, one or more range files that contain one or more clusters of cluster chains associated with the file may be created in the FAT. In some implementations, each range file can represent all clusters within one range of clusters that are part of a cluster chain. Due to the association between the range files and the clusters that contain the cluster chain, utilities such as chkdsk or fsck.vfat will not replace a discardable file with a non-disposable file and FAT recovery utilities will mark FAT32 entries that the file is a discardable file. Will not reset my flags.

FIG. 17 is a chart illustrating one or more range files created in a FAT, each storing at least one cluster of the cluster chain starting at entry 1602. For example, the first range file 1604 stores cluster # 7 and cluster # 9 from the cluster chain starting at entry 1602, and the second range file 1606 stores the cluster chain starting at entry 1602. Cluster # 13, cluster # 18, and cluster # 21 from the storage.

The scope file can store clusters from one or more cluster chains. For example, in addition to the clusters listed above from the cluster chain starting at entry 1602, the first range file 1604 can store cluster # 5 and cluster # 10 from the cluster chain starting at entry 1608. . Similarly, in addition to the clusters listed above from the cluster chain starting at entry 1602, the second scope file 1606 may include cluster # 16, cluster # 17, and cluster # 22 from the cluster chain starting at entry 1608. Can be saved.

18 illustrates a method of managing a storage device using a FAT in which an order of two or more clusters including a cluster chain is scrambled. FIG. 18 will be described with reference to FIG. 1. In operation 1810, the host 140 receives a request to store the file 142 in the storage device 100. At step 1820, storage allocator 144 marks the file as " disposable " or " non-disposable " in the file system structure associated with storage device 100 as described above. In step 1820, the file is also indicated that a discard priority level is assigned to the file.

In step 1830, when the file is a discardable file, storage allocator 144 updates the FAT to associate the cluster chain assigned to the file with the file. In step 1840, the order of two or more clusters in the cluster chain associated with the file may include, for example, the amount of memory in storage 100, the total size of the cluster chain, the number of clusters between two sequential clusters of the cluster chain, and And / or based on factors such as flash memory management algorithms that may take into account erase block size, the physical block address of each logical address in the assigned block, and / or wear leveling data for each page associated with the physical block address. It is scrambled in the FAT. In some implementations, the order of two or more clusters in a cluster chain is scrambled using a pseudo-random number generator or an entropy random number generator, which provides an offset within the range for each cluster that has not been previously assigned. In another implementation, the order of two or more clusters in the cluster chain is scrambled using a one-way hash function that takes into account non-deterministic values from host system 140 and / or storage device 100.

In step 1850, a first range file is created in the FAT that includes at least one cluster of the cluster chain associated with the first file. At step 1860, storage allocator 144 manages storage area 110 of storage device 100 (via communication with storage controller 120), or FAT stores files stored in storage area 110. And based on the location file.

In another implementation, the file system may implement a switch lock to prevent the discardable file from being converted to the non-discardable file while the discardable file is open. Discardable files may include, for example, a period of time during which the discardable file is being downloaded to storage device 100, such as before the release date associated with a movie, song, or program associated with the discardable file. As may be downloaded at 100), data associated with the discardable file may be open during the time before it is released to the public. In general, the switch lock operates so that a discardable file cannot be converted into a non-closable file when the switch lock is set.

19 is a method of using a conversion lock to prevent conversion of a disposable file when a disposable file is open in a file system implementing primary and discardable FAT. FIG. 19 will be described with respect to FIG. 1. At step 1910, storage allocator 144 receives a request to convert the discardable file to a non-discardable file. In step 1920, storage allocator 144 verifies the value of the switch lock identifier associated with the discardable file. At step 1930, storage allocator 144 determines whether the discardable file can be converted to the non-destructible file based on the value of the switch lock identifier. Typically, storage allocator 144 will determine that the discardable file may not be switched when the value of the switch lock identifier indicates that the discardable file is open, and storage allocator 144 will determine When the value indicates that the disposable file is not open, it will be determined that the disposable file can be converted.

If storage allocator 144 determines in step 1930 that the discardable file may not be converted to a non-disposable file, then storage allocator 144 may mark the discardable file as non-deletable in step 1940. It is forbidden. However, if storage allocator 144 determines in step 1930 that the discardable file may be converted to a non-disposable file, then storage allocator 144 may determine that the file associated with storage device 100 in step 1950. Mark the file as non-disposable in the system structure, update the primary FAT to reflect the physical location of the file in 1960, and update the discardable FAT to remove the physical location of the file in 1970 .

It will be appreciated that similar methods are implemented using the switch lock when a database or location file is used in the primary FAT instead of the disposable FAT as described above.

In some implementations, an application can perform operations such as converting a discardable file to a non-discardable file, or checking the value of a switch lock identifier based on an identifier associated with the application. Typically, an application that creates or downloads a discardable file may associate a user identifier (ID) with the discardable file. The user ID may be an owner user ID that identifies the application or user that created the discardable file. In some implementations, the owner user ID is a 4-byte value.

File system 160 has the ability to define what additional user IDs associated with other users or applications can access the discardable file and what actions the additional user IDs can take with respect to the discardable file. To the owner user ID. Depending on the use of the disposable file, it will be appreciated that additional user IDs may be associated with a single application or single user, or the additional user IDs may be shared user IDs associated with multiple applications or multiple users. .

In some implementations, the owner user ID can enable an application associated with the additional user ID to access the preview data associated with the discardable file. The preview data may be part of the discardable file associated with the preview data in other implementations but different from the discardable file. In some implementations, the discardable file can be a movie and the preview data can include a movie trailer associated with the movie; The discardable file may be a television program, and the preview data may include a portion of the television program; The discardable file may be music data and the preview data may include a portion of the music data; Alternatively, the discardable file may be a software program, and the preview data may include a demo version of the software program. In another implementation, the preview data may not be accessed before the release date associated with the discardable file, but the preview data associated with the discardable file may be accessed, and after the release date, both the discardable file and the preview data may be accessed. Can be used. In another example, the owner user ID can cause an application associated with the additional user ID to record the disposable file based on the user ID associated with the disposable file.

In some implementations, the file system can provide permission bit masks for the owner user ID to define what operations applications associated with the additional user ID will perform with respect to the discardable file. One example of permission bit masks for typical usage scenarios is shown in FIG. 20. However, it will be appreciated that the owner user ID may override any of the permissions shown in FIG. 20 and assign any permission to additional user IDs.

Referring to the permissions shown in FIG. 20, an application with the property write permission bit 2002 set may modify attributes such as enabling or disabling the transition lock, setting a time stamp, or recording a consumption intent universal resource indicator (URI). And an application with the property read permission bit 2004 set may read attributes such as a conversion lock, a time stamp, or a consumption intent URI. An application with the priority grant bit 2006 set may modify the priority level of the discardable file. An application with the preview read permission bit 2008 set may read the preview data associated with the discardable file, and an application with the preview write permission bit 2010 set the preview data associated with the discardable file. An application with the read permission bit 2012 set may read a discardable file, and an application with the write permission bit 2014 set may write to the discardable file. Typically, only applications associated with the owner user ID associated with the discardable file will have these permissions. An application for which the switch permission bit 2016 is set may convert the discardable file to the non-discardable file.

The method disclosed herein of displaying files and assigning revocation levels to them in an associated file system can have many useful applications, one of which is to recover storage usage safety margins to ensure sufficient storage space for user files. Note that For example, the discard level assigned to a file can be used to remap the file cluster to a low performance flash module or to clear the cluster on demand.

Smart Caching for Large Files

In addition to methods of managing data, also referred to as smart caching, described above, and in pending US patent application Ser. No. 12 / 336,089, filed Dec. 16, 2008, both of which are incorporated herein by reference and 2009 In addition to the descriptions and features of smart caching described in pending U.S. Provisional Patent Application No. 61 / 159,034, filed Mar. 10, 10, a smart caching technique for large discardable files is provided. This large file smart caching, also referred to herein as smart caching HD, includes several changes and extensions from the above. Smart Caching HD supports smart caching in support of these files by adding large file managers that intelligently handle the splitting of these files during conversion, while maintaining their large (> 4GB) state while files larger than 4GB can be discarded. Is different. In particular, this allows management and retrieval of the files described above as well as discarding them as single units rather than as a series of small files.

Ingredient

Smart caching components are described in the block diagram of FIG. Smart caching components 2100 may be operated in conjunction with any of a number of operating systems, such as ANDROID, WINDOWS or LINUX. Alternatively, the smart caching techniques discussed herein may be implemented on a storage medium such as a memory card without an operating system. A new component added for Smart Cache HD is a large file manager 2102 that handles files larger than 4GB in size. The large file manager is described in detail below.

Large Discardable Files

The file system containing the discardable file is conceptually configured as shown in the file system structure of FIG. The file system is similar in structure to the standard FAT32 file system found in SD-HC (and corresponding high capacity μSD) cards. Discardable Files In an HD implementation, the discardable file is stored in a shadow FAT.

Shadow FAT

The original two FAT tables allocate discardable clusters using only OxpFFFFFFF (EOF) or 0xp00000000 (unallocated) values that represent the file's priority, not the actual chain. If the most significant nibble is not zero, the third FAT table is referenced to determine the actual cluster chain sequence. Unlike the original two FAT tables, the Disposable FAT (DFAT) table can contain cluster chains longer than 4GB.

Directory  table

The directory entry for discardable files has the following elements. Elements that may be encrypted are represented in blobs as encrypted variants of the system, which may be unified into a binary large object. These fields are described here.

type Element name Integer (Primary Key) File ID essence Date / Time Generation Long integer Size (this is different from the smart cache implementation) Integer / Blob First cluster number Integer / Blob Owner user ID Integer / Blob Permission bitmap Integer / Blob preference Integer / Blob Preview type Integer / Blob Preview size Integer / Blob Preview number of clusters text Namespace text Filename Blob Billing Reference Integer / Blob Last cluster count Integer / Blob Last cluster count essence Expiration date byte activation text MIME type (this is different from the smart cache implementation)

Table 1: Discardable File Directory Entries

Note: The integer size is 32 bits. The long integer size is 64 bits.

Large file manager

Large File Manager (LFM) is a process handler implemented within Smart Caching HD to handle files larger than 4GB. Conceptually, the LFM consists of a file parser and a set of predefined partitioning algorithms, as shown in FIG. The LFM may be implemented on a host, or may be implemented on the storage device if other smart caching components are on the storage device.

The file parser uses known methods (such as those used in Linux file commands) to identify files, as well as refer to MIME types if they are stored in a disposable file directory entry. The type database is a simple table of file types and their corresponding split handlers, contained within the LFM. Additional split handlers may be included as needed, but three split handlers are shown. Typically, a split handler will have an interface for

Verify the structure of the discardable file;

Calculate the total number of segments the file will be split into (this would be the size of a file divided by 4GB typically, but file format constraints may require additional files);

Generate a header for each segment of the file;

Compute the offset of each segment boundary.

The actual division of the file is done during the conversion as described below.

Conversion flow

The conversion flow in smart caching HD is shown in FIG. 24. Process 2400 begins at step 2402 calling a convert () function by an application. The convert () function resumes the conversion process via a billing mechanism (as described in the smart caching application) at step 2404. If the switch is not authorized in step 2406, then a security exception is made in step 2407. If the switch is back in step 2406, the next step is to lock the file system in step 2408 so that other processes and device drivers do not modify it during the switch process, and allow the file system to refresh after the process is complete. will be. Subsequently, a cluster chain for the file to be converted is allocated from the FAT1 table and the FAT2 table of the volume and disconnected and needed from any existing placeholder file placed for dosfsck protection purposes in steps 2410 and 2412. If so, rearrange the cluster chain. If the file is less than 4 GB in total length in step 2414, a directory entry for the file is created in steps 2416, 2418, 2420, and 2422, and the file system is unlocked and refreshed in step 2424. In step 2426, the convert () flow ends.

If the file has a total length greater than 4 GB, the process proceeds to step 2428. Files larger than 4GB are generally HD media files, which can be divided into segments to be played sequentially. These segments can be linked together during playback to provide a seamless playback experience. However, a simple division of a file into 4 GB segments may cut the file in the middle of the frame, or one or more of the segments may lose the metadata (such as the file header) needed to identify or play the file. As such, each segment starts with a metadata header generated by a format-compliant LFM. Some file types are not, of course, divided into segments such as documents or executables, and these files cannot be converted to smaller segments using this strategy. For these files, large file managers may use compression libraries, such as ZIP, that support splitting while maintaining the order of the files. The large file manager uses the flow shown in FIG. 25 when switching files.

The process 2500 for managing a file of length greater than 4GB begins at step 2502, requesting a switch by the application. The header of the file is read at step 2504 and it is determined at step 2506 whether the file is of known type. If the file is not of known type, the process proceeds to step 2508 where the file is spanned into a plurality of files using the general method and the conversion process and the conversion process continues to the file spanned at step 2510.

If the file is of known type in step 2506, then it is determined in step 2512 whether the file type supports spanning into multiple files. If the file type supports spanning to a file, the file is spanned into a plurality of files using a method specific to the file type in step 2514 before proceeding to step 2510. However, if the file type does not support spanning to a file, the file is spanned into multiple files using the general method at step 2508 before proceeding to step 2510.

As an example of a file type specific method, FIG. 26 is a simplified illustration of an open source Matroska (mkv) container file format, commonly used in high definition video streams. A Matroska file typically consists of a file header (extensible binary meta-language (EBML) header) followed by one segment, and tags. To divide these files, the segment itself is divided into a plurality of files, each of which has its own EBML header and segment header. Within the segment header are the following fields to help link the split file:

Field name type Explanation SegmentUID GUID (128 bit number) Unique 128-bit number identifying the segment. Obviously, a file can only be referenced by another file if there is a segment, but it can be played without this UID. SegmentFileName Character string File name where the segment is stored PrevUID GUID Unique 128-bit GUID of previous segment (segment with timecode before current segment) PrevFilename Character string File name with previous segment NextUID GUID Unique 128-bit GUID of the next segment NextFilename Character string File name with next segment

Table 2: Segment Information Structure (some)

The process of splitting a Matroska file involves assigning and creating a new MKV file for each segment, and attaching an EBML header and a rewritten segment header to each segment.

Large file managers include support for performing explicit in-place splits on file types for various file types, such as Matroska, in each case by using a specific split handler for each file type. Alternate partitioning adds a cluster to a cluster chain containing new header information, as shown in FIG. 27, without moving data within the file, and then adds a new directory entry for each file to create a plurality of cluster chains. This is done by splitting into files and assigning FCNs to each file at appropriate points in the chain. (The number of clusters just before the FCN in the chain will point to the EOF indicator). For other file types there is a similar flow implied within the large file manager. The large file manager automatically detects the file type and generates an alternative generation accordingly.

The present application includes methods and systems for managing storage devices. In one implementation, a storage allocator at the host or storage device receives a request to store a file in a storage area of the storage device. The storage allocator marks the file as discardable in the file system structure associated with the storage device and updates the main file allocation table ("FAT") to associate the cluster chain assigned to the file with the file. In addition, the storage allocator may update a discardable FAT or database to reflect the physical location of the file, or generate one or more location files that store the physical location of the file. The storage allocator manages storage area devices based on one or more location files representing the physical location of the FAT and the discardable FAT, database, or file.

Many methods and systems have been disclosed above and can be implemented in many ways. Some examples of combinations of implementations are provided for understanding, but these are not limiting and additional features and combinations are also contemplated.

In one implementation, a first method of managing storage comprises receiving, at a host to which the storage device is operatively coupled, a request to store a first file in a storage area of a storage device containing a primary FAT and a disposable FAT. step; Marking the first file as discardable, wherein marking the first file is performed on a file system structure associated with the storage device; Causing the storage device to update the primary FAT to associate the cluster chain assigned to the first file with the first file; Causing the storage device to update the discardable FAT to reflect the physical location of the first file on the storage device; And managing a storage area of the storage device according to the disposable FAT.

In this method, the cluster chain masks at least the physical location of the first file, and the cluster chain of the primary FAT may point to a location in the discardable FAT. Managing the storage area of the storage device according to the discardable FAT includes recovering a storage use safety margin by selectively removing one or more files marked as discardable; Emptying the storage area by removing all files marked as discardable; Or remapping the cluster of the first file to the low-performance storage module or a combination thereof.

The first method may also include activating an attribute associated with the first file to prevent the host operating system from accessing the first file. Alternatively, the first method includes receiving a request to store a second file in a storage area of the storage device; Marking the second file as discardable, wherein marking the second file is done in a file system structure associated with the storage device; Causing the storage device to update the primary FAT to associate the cluster chain associated with the first file and the second file with the second file; And causing the storage device to update the discardable FAT to reflect the physical location of the second file. The cluster chain may mask the physical locations of the first file and the second file.

The first method above includes receiving a request to store a second file in a storage area of the storage device; Marking the second file as discardable, wherein marking the second file is done in a file system structure associated with the storage device; Causing the storage device to update the primary FAT to associate the second cluster chain assigned to the second file with the second file; And causing the storage device to update the discardable FAT to reflect the physical location of the second file.

Alternatively, the first method includes marking the first file as a non-discardable file, wherein the marking of the first file is done in a file system structure associated with the storage device; Causing the storage device to update the primary FAT to reflect the physical location of the first file; And causing the storage device to update the discardable FAT to remove the physical location of the first file. This alternative to the first method may further comprise checking a value of the conversion lock identifier associated with the first file to determine whether the first file can be converted from the discardable file to the non-disposable file, the first file Is marked as a non-discardable file after determining that the value of the switch lock identifier associated with the first file indicates that the first file is not locked.

In yet another alternative of the first method, the method further comprises: checking a value of the switch lock identifier associated with the first file to determine whether the first file can be converted from the discardable file to the non-discardable file; And prohibiting marking the first file as discardable after determining that the value of the switch lock associated with the first file indicates that the first file is locked. Alternatively, the first method includes identifying file permissions associated with the user ID and a preview file associated with the first file, and managing access to the preview file associated with the first file based on the identified file permissions. It may include. The user ID may be a shared user ID.

In a first method, marking the first file as discardable may include assigning a discard priority level to the first file. In addition, assigning a discarding priority level to the first file includes setting a corresponding value to the m most significant bits in the primary FAT entry corresponding to the first file, or a corresponding file system to the first file. It may include at least one of setting in the data field in the entry. The revocation priority level may include the expected use of the first file; The first file may be assigned to the first file according to any one of an expected revenue associated with using the file, a file type of the first file, a size of the first file, a location of the first file in the storage device, and a storage period of the first file. .

In another implementation, a second method of managing storage includes receiving, at a host to which the storage device is operatively coupled, a request to store a first file in a storage area of a storage device containing a primary FAT and a disposable FAT. step; Marking the first file as discardable, wherein marking the first file is performed on a file system structure associated with the storage device; Updating the primary FAT to associate the cluster chain assigned to the first file with the first file; Updating the disposable FAT to reflect the physical location of the first file on the storage device; And managing a storage area of the storage device according to the disposable FAT. The cluster chain may mask at least the physical location of the first file. The second method may further comprise activating an attribute associated with the first file to prevent the host operating system from accessing the first file. The cluster chain of the primary FAT can point to a location within the discardable FAT.

In one variation, the second method includes receiving a request to store a second file in a storage area of the storage device; Marking the second file as discardable in a file system structure associated with the storage device; Updating the primary FAT to associate the cluster chains associated with the first file and the second file with the second file; And updating the discardable FAT to reflect the physical location of the second file. In this variant, the cluster chain may mask the physical locations of the first file and the second file.

In yet another implementation, a second method includes receiving a request to store a second file in a storage area of a storage device; Marking the second file as discardable in a file system structure associated with the storage device; Updating the primary FAT to associate the second cluster chain assigned to the second file with the second file; And updating the discardable FAT to reflect the physical location of the second file.

Alternatively, the second method includes marking the first file as a non-discardable file in a file system structure associated with the storage device; Updating the primary FAT to reflect the physical location of the first file; And updating the discardable FAT to remove the physical location of the first file. This alternative to the second method may further comprise checking a value of the conversion lock identifier associated with the first file to determine whether the first file can be converted from the discardable file to the non-disposable file, the first file Is marked as a non-discardable file after determining that the value of the switch lock identifier associated with the first file indicates that the first file is not locked.

Another variant of the second method further comprises: checking a value of a switch lock identifier associated with the first file to determine whether the first file can be converted from the discardable file to the non-discardable file; And prohibiting marking the first file as a non-discardable file after determining that the value of the switch lock associated with the first file indicates that the first file is locked. Another second version includes identifying a file permission associated with the user ID and a preview file associated with the first file; And managing access to the preview file associated with the first file based on the identified file permission. The user ID may be a shared user ID.

In a second method, marking the first file as discardable may include assigning a discard priority level to the first file. Assigning a discard priority level to the first file comprises setting a corresponding value to the m most significant bits in the primary FAT entry corresponding to the first file, or setting the corresponding value in the file system entry corresponding to the first file. It may include at least one of setting in the data field. Alternatively, the discard priority level may include the expected use of the first file; The first file may be assigned to the first file according to any one of an expected revenue associated with using the file, a file type of the first file, a size of the first file, a location of the first file in the storage device, and a storage period of the first file. .

In a second method, managing the storage area of the storage device in accordance with the discardable FAT includes recovering a storage use safety margin by selectively removing one or more files marked as discardable; Emptying the storage area by removing all files marked as discardable; Or remapping the cluster of the first file to the low-performance storage module or a combination thereof.

The storage allocator for managing the storage device includes a communication interface for interfacing with the storage device and a host of the storage device; A storage unit for storing a file system associated with the storage device; And a processor for managing a file system associated with the storage device, the processor receiving a request to store the first file in a storage area of the storage device containing the primary FAT and the disposable FAT; Marking the first file as discardable, wherein marking the first file is done in a file system structure associated with the storage device; Cause the storage device to update the primary FAT to associate the cluster chain assigned to the first file with the first file; Cause the storage device to update the discardable FAT to reflect the physical location of the first file on the storage device; The storage area of the storage device is configured according to the disposable FAT. The cluster chain masks the physical location of the first file. The cluster chain of the first FAT may point to a location in the second FAT.

In the alternative, the processor receives a request to store a second file in a storage area of the storage device; Mark the second file as discardable in a file system structure associated with the storage device; Have the storage device update the primary FAT to associate the cluster chain associated with the first file and the second file with the second file; The storage device may be further configured to update the second FAT to reflect the physical location of the second file, and the discardable cluster chain masks the physical location of the first file and the second file.

In another variation of the storage allocator mentioned above, the processor receives a request to store a second file in a storage area of the storage device and marks the second file as discardable in a file system structure associated with the storage device; A processor further configured to cause the storage device to update the primary FAT to associate the second cluster chain assigned to the second file to the second file, and cause the storage device to update the recyclable FAT to reflect the physical location of the second file. It may be provided. In addition, the processor may be further configured to verify the value of the switch lock identifier associated with the first file to determine whether the first file can be converted from the discardable file to the non-disposable file, the first file being located in the first file. After the value of the associated switch lock identifier determines that the first file is not locked, it is marked as a non-discardable file.

In another implementation, the storage allocator checks the value of the switch lock identifier associated with the first file to determine whether the first file can be switched from the discardable file to the non-discardable file; The processor may be configured to prohibit marking the first file as a non-discardable file after determining that the value of the switch lock associated with the first file indicates that the first file is locked. In the alternative, the processor of the storage allocator identifies file permissions associated with the user ID and the preview file associated with the first file; And may be further configured to access a preview file associated with the first file based on the identified file permissions.

Communication interface; And a storage allocator for managing a file system associated with the storage device. The storage allocator may include a processor that manages the storage of one or more files in a storage area of the storage device, which processor is configured in the same manner as the storage allocator described above. In different implementations, the storage allocator of the storage system can be embedded in a host or storage device. The storage system may be arranged such that the processor is configured to derive the request to save the first file based on one or more write requests associated with the first file received via the communication interface to receive the request via the communication interface. .

A third method of managing a storage device is disclosed, the method comprising: receiving, at a host to which the storage device is operatively coupled, a request to store a first file in a storage area of the storage device; Marking the first file as discardable in a file system structure associated with the storage device; Causing the storage device to update the FAT to associate the cluster chain assigned to the first file with the first file; Updating the database to reflect the physical location of the first file on the storage device; And managing a storage area of the storage device according to the FAT and the database.

A fourth method of managing storage devices includes receiving, at a storage device operatively coupled to a host, a request to store a first file in a storage area of the storage device; Marking the first file as discardable, wherein marking the first file is done in a file system structure associated with the storage device; Updating the FAT to associate the cluster chain assigned to the first file with the first file; Updating the database to reflect the physical location of the first file on the storage device; And managing a storage area of the storage device according to the FAT and the database.

The fifth method of managing the storage device includes the steps related to the steps of the fourth method disclosed above from the host's point of view, not from the storage device. In particular, the fifth method includes receiving, at a host to which the storage device is operatively coupled, a request to store a first file in a storage area of the storage device; Marking the first file as discardable in a file system structure associated with the storage device; Causing the storage device to update the FAT to associate the cluster chain assigned to the first file with the first file; Updating the location file to reflect the physical location of the first file on the storage device; And managing a storage area of the storage device according to the FAT and the location file. The location file may be a file such as a text file or a binary file.

A sixth method of managing a storage device includes receiving, at a host to which the storage device is operatively coupled, a request to store a first file in a storage area of the storage device; Marking the first file as discardable in a file system structure associated with the storage device; Causing the storage device to update the FAT to associate the cluster chain assigned to the first file with the first file; Scramble the order of two or more clusters of the cluster chains associated with the first file in the FAT; Creating a first range file in a FAT that includes at least one cluster of a cluster chain associated with the first file; And managing a storage area of the storage device according to the FAT and the first range file.

The sixth method includes receiving a request to store a second file in a storage area of the storage device; Marking the second file as discardable in a file system structure associated with the storage device; Causing the storage device to update the FAT to associate the cluster chain associated with the first file and the second file with the second file; And scrambled the order of two or more clusters of the cluster chain associated with the second file in the FAT. Further, the sixth method may further comprise updating the first range file to a FAT that includes at least one cluster of the cluster chain associated with the second file.

In a variation of the sixth method, the method includes receiving a request to store a second file in a storage area of the storage device; Marking the second file as discardable in a file system structure associated with the storage device; Causing the storage device to update the FAT to associate the second cluster chain assigned to the second file with the second file; Scrambled the order of two or more clusters in the cluster chain associated with the second file in the FAT; The method may further include generating a second range file in a FAT including at least one cluster of a cluster chain associated with the second file, wherein managing the storage area of the storage device according to the FAT and the first range file is FAT. Managing a storage area of the storage device according to the first range file and the second range file.

In another variation of the sixth method, the method may further comprise generating a second range file in a FAT having at least one cluster in a cluster chain associated with the first file that does not include the first range file, Managing the storage area of the storage device according to the FAT and the first range file includes managing the storage area of the storage device according to the FAT, the first range file and the second range file.

The seventh method of managing the storage device includes the steps related to the steps of the sixth method disclosed above from the host's point of view, not from the storage device. In particular, the seventh method includes receiving, at a storage device coupled to a host, a request to store a first file in a storage area of the storage device; Marking the first file as discardable, wherein marking the first file is done in a file system structure associated with the storage device; Updating the FAT to associate the cluster chain assigned to the first file with the first file; Scramble the order of two or more clusters of the cluster chains associated with the first file in the FAT; Creating a first range file in a FAT that includes at least one cluster of a cluster chain associated with the first file; And managing a storage area of the storage device according to the FAT and the first range file. A variant of the seventh method is similar to the example of the sixth method mentioned above.

According to an eighth method, a method for managing operations associated with a discardable file on a host to which the storage device is operatively coupled includes an owner user ID in a discardable file that includes a file marked as discardable in a file system structure associated with the storage device. Associating; Defining, with an application associated with the owner user ID, a set of permissions for additional user IDs associated with the discardable file; Receiving a request from an application associated with the additional user ID to perform an operation associated with the discardable file; Determining whether an application associated with the additional user ID can perform an action based on a set of permissions; And managing an action associated with the discardable file based on the determination.

In a variation of the eighth method, the application associated with the owner user ID can download the discardable file to the storage device. Alternatively, the operation associated with the disposable file may include modifying an attribute associated with the disposable file. In another variation of the eighth method, the method may further comprise reading an attribute associated with the discardable file. The attribute may be at least one of a switch lock identifier, a time stamp, a consumption intention universal resource indicator (URI), or a priority level. In another variant of the eighth method, the operation may include reading the disposable file, writing to the disposable file, writing preview data associated with the disposable file, or reading preview data associated with the disposable file. It may include. The discardable file may include preview data or may be distinguished from preview data in different implementations.

The additional user ID of the eighth method may be a shared user ID associated with the plurality of users. Alternatively, the additional user ID of the eighth method may be a shared user ID associated with the plurality of applications. In one further variant of the eighth method, managing the action associated with the discardable file based on the determination may include inhibiting an application associated with the further user ID from performing the action associated with the discardable file. Can be. In yet further variations, managing the action associated with the discardable file based on the determination includes enabling an application associated with the additional user ID to perform an action associated with the discardable file.

Also contemplated is a storage system having a communication interface and a storage allocator for managing file systems associated with the storage device. The storage allocator may include a processor that manages operations associated with the discardable file stored on the storage device, and the processor assigns an owner user ID to the discardable file that includes the file marked as discardable in the file system structure associated with the storage device. To associate; An application associated with the owner user ID, defining a set of permissions for additional user IDs associated with the discardable file; Receive, via the communication interface, a request from the application associated with the additional user ID to perform an operation associated with the discardable file; Determine whether an application associated with the additional user ID can perform an action based on a set of permissions; And manage operations associated with the discardable file based on the determination. In order to manage operations associated with the discardable file, the processor may be configured to allow an application associated with the additional user ID to read preview data associated with the discardable file. The additional user ID may be a shared user ID associated with the plurality of users or a shared user ID associated with the plurality of applications.

A ninth method for managing a storage device comprises: storing preview data in the storage device at a host to which the storage device is operatively coupled; Associating preview data with a discardable file that is a file marked as discardable in a file system structure associated with the storage device; Managing access to the preview data and the discardable file to allow the application to access the preview data but not to access the discardable file. The discardable file may be preview data that is distinct from the preview data. In an alternative implementation of the ninth method, the discardable file may be a movie and the preview data may be a movie trailer associated with the movie, the discardable file may be a television program, the preview data may be part of a television program, The discardable file may be music data, the preview data may be part of the music data, or the discardable file may be a program, and the preview data may be a demo version of the program.

In one alternative implementation of the ninth method, managing access to the preview data and the discardable file to allow the application to access the preview data but not to access the discardable file includes a release date associated with the discardable file. Managing access to the preview data and the discardable file before allowing the application to access the preview data for a period of time but not accessing the discardable file.

Download management

In addition to the data management methods, also referred to above as smart caching and smart caching HD, smart cache techniques are provided to manage the download of discardable files in a storage area of the storage device. In general, a download manager, which may be part of the storage allocator described above in some implementations, such as the type of network that can be used to download disposable files to the storage device, the power state available to the storage device, and the discardable storage device. Based on the download status, such as the time associated with the request to download the file and / or available storage associated with the storage device, it may be determined whether to delay the download to the storage area of the storage device of the discardable file.

For example, the download manager may decide to delay the download of the discardable file until the WiFi network and / or cellular network are available to download the discardable file. Similarly, the download manager may determine not to delay the download of discardable files while the device is coupled to a power source or the power level of the battery associated with the storage device is above a predetermined level, but the download manager may not delay the download of the discardable file. May charge, and / or delay the download of the discardable file while the power level of the battery associated with the storage device is below a predetermined level. In addition, the download manager may decide to delay the download of discarded files that are requested during business hours during which network congestion may be high until evening, such as when the network is not mixed, such as after 8 pm, or the download manager may You may decide to delay the download of the discardable file requested on one day by one day during the weekend. In addition, the download manager may delay downloading the discardable file until the amount of storage available in the storage device is above a predetermined level before storing the discardable file in the storage area of the storage device.

28 is a flowchart of a method of managing download of discardable files in a storage area of a storage device. In step 2802, a request is received to store a file in a storage area of the storage device, where the file is a disposable file and associated with data in a data structure associated with the storage device. In some implementations, the data structure can include a file system structure. In step 2804, the file is marked as "disposable file." In some implementations, the file system structure of the data structure is indicated to indicate that the file is a discardable file. In another implementation, the file itself is marked to indicate that the file is a discardable file.

In step 2806, the download manager, which may be part of the storage allocator in some implementations, determines the download status associated with the request to store the discardable file in a storage area of the storage device. For example, the download manager can use the type of network that can be used to download discardable files to the storage device, the power state available to the storage device when downloading the discardable files to the storage device, and discard them to the storage area of the storage device. The time associated with the request to store the possible file may be determined and / or the amount of storage space available to the storage device may be determined.

In step 2808, the download manager determines whether to delay the download to the storage of discardable files based on the determined download state, and in step 2810, the download manager downloads the discardable files to the storage device. Manage the download of discardable files to the storage device based on the determination of whether to delay. In step 2810, the download manager may delay the download of the discardable file to the storage device until a parameter associated with the download state is satisfied. For example, the download manager may delay the download of the discardable file until the WiFi network and / or cellular network are available to download the discardable file to the storage device, which may cause the storage device to be coupled to a power source, or The download of the discardable file may be delayed until the power level of the battery associated with the storage device is above a predetermined level, and / or the download manager may save the discardable file to the storage device before storing it in the storage area of the storage device. The download of the discardable file can be delayed until the available storage amount is above a predetermined level.

In step 2812, a storage allocator, which may include a download manager, manages storage of downloaded discardable files in a storage area of the storage device based on indicating that the file is a disposable file as described above.

In some implementations, one or more processors can be configured to perform the operations described above with respect to FIG. 28 based on instructions stored in a memory, such as a computer-readable non-transitory storage medium. One or more processors may be located in a host, a storage device, or a combination thereof.

The method disclosed herein of displaying files and assigning revocation levels to them in the associated file system can have many useful applications, one of which is to recover the storage usage safety margin to ensure sufficient storage space for user files. Note that For example, the discard level assigned to a file can be used to remap the file cluster to a low performance flash module or to clear the cluster on demand.

Singular expression is used herein to refer to one or more (ie at least one) depending on the context. By way of example, depending on the context, an “element” may mean one element or more than one element. The term "comprises" is used herein to mean "including but not limited to" and is used interchangeably. The terms "or" and "and" are used herein interchangeably with the terms "and / or" unless the context clearly indicates otherwise. The term "such as" is used herein to mean "but not limited to," and is used interchangeably herein.

As such, it will be apparent to those skilled in the art that embodiments of the invention have been described and modifications of the disclosed embodiments will fall within the scope of the invention. Thus, alternative embodiments may include more modules, fewer modules, and / or functionally equivalent modules. The present disclosure includes, for example, SD-driven flash memory cards, flash storage devices, non-flash storage devices, "disk-on-key" devices with Universal Serial Bus (USB) interfaces, USB flash drives ("UFDs"), It relates to various types of mass storage devices such as multimedia cards ("MMC"), secure digital ("SD"), mini SD, micro SD, and the like. The scope of the following claims is not limited by the disclosure herein. The following detailed description, therefore, is not to be taken in a limiting sense, and the following claims, which are regarded as illustrative and include all equivalents, are intended to define the spirit and scope of the present invention.

Claims (28)

In the method of managing the storage device,
On the host where the storage device is operatively coupled,
Receiving a request to store a file in a storage area of the storage device, the file being a discardable file, associating the file with data in a data structure associated with the storage device;
Marking the file as a "discardable file";
Determining a download state associated with a request to store the discardable file in a storage area of the storage device;
Determining whether to delay downloading of the discardable file to the storage device based on the determined download state;
Managing download of the discardable file on the storage device based on the determination of whether to delay the download of the discardable file to the storage device;
Managing storage of the downloaded discardable file in a storage area of the storage device based on an indication that the file is a discardable file;
A storage device management method comprising. The storage device of claim 1, wherein managing the download of the discardable file comprises delaying the download of the discardable file to the storage device until a parameter associated with the download state is satisfied. How to manage. The method of claim 1, wherein determining a download status associated with the request to store discardable files in a storage area of the storage device further comprises determining a type of network that can be used to download the discardable files to the storage device. And storing the storage device. 4. The method of claim 3, wherein determining the type of network that can be used to download the discardable file to the storage device may include using a wireless fidelity network to download the discardable file to the storage device. Determining whether there is a storage device management method. 4. The method of claim 3, wherein determining the type of network that can be used to download the discardable file to the storage device comprises: determining whether a cellular network can be used to download the discardable file to the storage device. Comprising a storage device management method. The method of claim 1, wherein determining a download state associated with the request to store discardable files in a storage area of the storage device is available to the storage device when downloading the discardable files to the storage device. Determining the power state. 7. The method of claim 6, wherein determining the power state available to the storage device when downloading the discardable file to the storage device comprises determining that the storage device is coupled to a power source. How to manage your device. The method of claim 6, wherein determining the power state available for the storage device when downloading the discardable file to the storage device includes determining that a battery associated with the storage device is charged. How to manage storage devices. 7. The method of claim 6, wherein determining the power state available for the storage device when downloading the discardable file to the storage device comprises determining that the power level of a battery associated with the storage device is greater than or equal to a predetermined level. And storing the storage device. 2. The method of claim 1, wherein determining a download state associated with the request to store discardable files in the storage area of the storage device comprises: time associated with the request to store discardable files in the storage area of the storage device. determining a time of day). 2. The method of claim 1, wherein determining a download state associated with the request to store discardable files in the storage area of the storage device comprises: storing the discardable files in the storage area of the storage device before storing them in the storage area. And determining that the available storage amount is above a predetermined level. The method of claim 1, wherein the data structure comprises a file system structure associated with the storage device. 13. The method of claim 12, wherein the file system structure is displayed to indicate that the file is a discardable file. The method of claim 1, wherein the file itself is displayed to indicate that the file is a discardable file. In a storage system,
Communication interface,
A processor for managing storage of one or more files in a storage area of a storage device, the processor comprising:
Receiving a request to store a file in a storage area of the storage device, wherein the file is a discardable file and associates the file with data in a data structure associated with the storage device. Receive a request to save,
Mark the file as "disposable file",
Determine a download state associated with the request to store a discardable file in a storage area of the storage device,
Determine whether to delay downloading of the discardable file to the storage device based on the determined download state,
Manage the download of the discardable file on the storage device based on the determination of whether to delay the download of the discardable file to the storage device,
To manage storage of the downloaded discardable file in a storage area of the storage device based on an indication that the file is a discardable file
Configured, the processor
Including, storage system. The storage system of claim 15, wherein to manage download of the discardable file, the processor is further configured to delay the download of the discardable file to the storage device until a parameter associated with the download state is satisfied. . The network of claim 15, wherein the processor is configured to determine a download state associated with the request to store the discardable file in a storage area of the storage device that the processor can use to download the discardable file to the storage device. A storage system, further configured to determine the type. 18. The method of claim 17, wherein to determine the type of network that can be used to download the discardable file to the storage device, the processor is configured to: a wireless fidelity (WiFi) network to download the discardable file to the storage device. The storage system is further configured to determine if it can be used. 18. The method of claim 17, wherein to determine the type of network that can be used to download the discardable file to the storage device, the processor determines whether a cellular network can be used to download the discardable file to the storage device. And further configured to determine. 16. The processor of claim 15, wherein the processor is configured to download the discardable file to the storage device to determine a download state associated with the request to store the discardable file in a storage area of the storage device. The storage system is further configured to determine the available power state. The processor of claim 20, wherein the processor is further configured to determine that the storage device is coupled to a power source to determine a power state available to the storage device when downloading the discardable file to the storage device. Storage system. The processor of claim 20, wherein the processor is further configured to determine that a battery associated with the storage device is charged to determine a power state available to the storage device when downloading the discardable file to the storage device. , Storage system. The processor of claim 20, wherein the processor is further configured to determine a power state available to the storage device when downloading the discardable file to the storage device, wherein the power level of the battery associated with the storage device is greater than or equal to a predetermined level. And further configured to determine that the storage system is configured. 16. The method of claim 15, wherein to determine a download status associated with the request to store a discardable file in a storage area of the storage device, the processor is further configured to: store the discardable file in the storage area of the storage device; And further configured to determine the associated time of day. The processor of claim 15, wherein the processor is further configured to determine a download state associated with the request to store the discardable file in a storage area of the storage device, before storing the discardable file in the storage area of the storage device. And further configured to determine that the amount of storage available to the storage device is above a predetermined level. The storage system of claim 15, wherein the data structure includes a file system structure associated with the storage device. 27. The storage system of claim 26, wherein the file system structure is displayed to indicate that the file is a discardable file. The storage system of claim 15, wherein the file itself is displayed to indicate that the file is a discardable file.

Images