94  * insert_in_sorted_list() - Insert a bin to the list.
96  * @bin: The bin to move to its sorted position.
99  * actually moves the bin to the correct position in the list.
101 static void insert_in_sorted_list(struct packer *packer, struct packer_bin *bin)  in insert_in_sorted_list()  argument
106 		if (active_bin->free_space > bin->free_space) {  in insert_in_sorted_list()
107 			list_move_tail(&bin->list, &active_bin->list);  in insert_in_sorted_list()
111 	list_move_tail(&bin->list, &packer->bins);  in insert_in_sorted_list()
115  * make_bin() - Allocate a bin and put it into the packer's list.
120 	struct packer_bin *bin;  in make_bin()  local
124 				       struct vio *, __func__, &bin);  in make_bin()
128 	bin->free_space = VDO_COMPRESSED_BLOCK_DATA_SIZE;  in make_bin()
129 	INIT_LIST_HEAD(&bin->list);  in make_bin()
130 	list_add_tail(&bin->list, &packer->bins);  in make_bin()
167 	 * The canceled bin can hold up to half the number of user vios. Every canceled vio in the  in vdo_make_packer()
168 	 * bin must have a canceler for which it is waiting, and any canceler will only have  in vdo_make_packer()
194 	struct packer_bin *bin, *tmp;  in vdo_free_packer()  local
199 	list_for_each_entry_safe(bin, tmp, &packer->bins, list) {  in vdo_free_packer()
200 		list_del_init(&bin->list);  in vdo_free_packer()
201 		vdo_free(bin);  in vdo_free_packer()
321  * @bin: The bin in which to put the data_vio.
324 static void add_to_bin(struct packer_bin *bin, struct data_vio *data_vio)  in add_to_bin()  argument
326 	data_vio->compression.bin = bin;  in add_to_bin()
327 	data_vio->compression.slot = bin->slots_used;  in add_to_bin()
328 	bin->incoming[bin->slots_used++] = data_vio;  in add_to_bin()
332  * remove_from_bin() - Get the next data_vio whose compression has not been canceled from a bin.
334  * @bin: The bin from which to get a data_vio.
336  * Any canceled data_vios will be moved to the canceled bin.
337  * Return: An uncanceled data_vio from the bin or NULL if there are none.
339 static struct data_vio *remove_from_bin(struct packer *packer, struct packer_bin *bin)  in remove_from_bin()  argument
341 	while (bin->slots_used > 0) {  in remove_from_bin()
342 		struct data_vio *data_vio = bin->incoming[--bin->slots_used];  in remove_from_bin()
345 			data_vio->compression.bin = NULL;  in remove_from_bin()
352 	/* The bin is now empty. */  in remove_from_bin()
353 	bin->free_space = VDO_COMPRESSED_BLOCK_DATA_SIZE;  in remove_from_bin()
419  * write_bin() - Write out a bin.
421  * @bin: The bin to write.
423 static void write_bin(struct packer *packer, struct packer_bin *bin)  in write_bin()  argument
430 	struct data_vio *agent = remove_from_bin(packer, bin);  in write_bin()
443 	while ((client = remove_from_bin(packer, bin)) != NULL)  in write_bin()
490  * add_data_vio_to_packer_bin() - Add a data_vio to a bin's incoming queue
492  * @bin: The bin to which to add the data_vio.
493  * @data_vio: The data_vio to add to the bin's queue.
495  * Adds a data_vio to a bin's incoming queue, handles logical space change, and calls physical
498 static void add_data_vio_to_packer_bin(struct packer *packer, struct packer_bin *bin,  in add_data_vio_to_packer_bin()  argument
501 	/* If the selected bin doesn't have room, start a new batch to make room. */  in add_data_vio_to_packer_bin()
502 	if (bin->free_space < data_vio->compression.size)  in add_data_vio_to_packer_bin()
503 		write_bin(packer, bin);  in add_data_vio_to_packer_bin()
505 	add_to_bin(bin, data_vio);  in add_data_vio_to_packer_bin()
506 	bin->free_space -= data_vio->compression.size;  in add_data_vio_to_packer_bin()
508 	/* If we happen to exactly fill the bin, start a new batch. */  in add_data_vio_to_packer_bin()
509 	if ((bin->slots_used == VDO_MAX_COMPRESSION_SLOTS) ||  in add_data_vio_to_packer_bin()
510 	    (bin->free_space == 0))  in add_data_vio_to_packer_bin()
511 		write_bin(packer, bin);  in add_data_vio_to_packer_bin()
514 	insert_in_sorted_list(packer, bin);  in add_data_vio_to_packer_bin()
518  * select_bin() - Select the bin that should be used to pack the compressed data in a data_vio with
527 	 * First best fit: select the bin with the least free space that has enough room for the  in select_bin()
530 	struct packer_bin *bin, *fullest_bin;  in select_bin()  local
532 	list_for_each_entry(bin, &packer->bins, list) {  in select_bin()
533 		if (bin->free_space >= data_vio->compression.size)  in select_bin()
534 			return bin;  in select_bin()
540 	 * the fullest bin, since that "wastes" the least amount of free space in the compressed  in select_bin()
541 	 * block. But if the space currently used in the fullest bin is smaller than the compressed  in select_bin()
542 	 * size of the incoming block, it seems wrong to force that bin to write when giving up on  in select_bin()
551 	 * The fullest bin doesn't have room, but writing it out and starting a new batch with the  in select_bin()
565 	struct packer_bin *bin;  in vdo_attempt_packing()  local
597 	 * the data_vio is in the DATA_VIO_PACKING state, it must be guaranteed to be put in a bin  in vdo_attempt_packing()
601 	 * actually add the data_vio to a bin before advancing to the DATA_VIO_PACKING stage.  in vdo_attempt_packing()
603 	bin = select_bin(packer, data_vio);  in vdo_attempt_packing()
604 	if ((bin == NULL) ||  in vdo_attempt_packing()
610 	add_data_vio_to_packer_bin(packer, bin, data_vio);  in vdo_attempt_packing()
629 	struct packer_bin *bin;  in write_all_non_empty_bins()  local
631 	list_for_each_entry(bin, &packer->bins, list)  in write_all_non_empty_bins()
632 		write_bin(packer, bin);  in write_all_non_empty_bins()
634 		 * We don't need to re-sort the bin here since this loop will make every bin have  in write_all_non_empty_bins()
666 	struct packer_bin *bin;  in vdo_remove_lock_holder_from_packer()  local
672 	bin = lock_holder->compression.bin;  in vdo_remove_lock_holder_from_packer()
673 	VDO_ASSERT_LOG_ONLY((bin != NULL), "data_vio in packer has a bin");  in vdo_remove_lock_holder_from_packer()
676 	bin->slots_used--;  in vdo_remove_lock_holder_from_packer()
677 	if (slot < bin->slots_used) {  in vdo_remove_lock_holder_from_packer()
678 		bin->incoming[slot] = bin->incoming[bin->slots_used];  in vdo_remove_lock_holder_from_packer()
679 		bin->incoming[slot]->compression.slot = slot;  in vdo_remove_lock_holder_from_packer()
682 	lock_holder->compression.bin = NULL;  in vdo_remove_lock_holder_from_packer()
685 	if (bin != packer->canceled_bin) {  in vdo_remove_lock_holder_from_packer()
686 		bin->free_space += lock_holder->compression.size;  in vdo_remove_lock_holder_from_packer()
687 		insert_in_sorted_list(packer, bin);  in vdo_remove_lock_holder_from_packer()
744 static void dump_packer_bin(const struct packer_bin *bin, bool canceled)  in dump_packer_bin()  argument
746 	if (bin->slots_used == 0)  in dump_packer_bin()
751 		     (canceled ? "Canceled" : ""), bin->slots_used, bin->free_space);  in dump_packer_bin()
754 	 * FIXME: dump vios in bin->incoming? The vios should have been dumped from the vio pool.  in dump_packer_bin()
767 	struct packer_bin *bin;  in vdo_dump_packer()  local
775 	list_for_each_entry(bin, &packer->bins, list)  in vdo_dump_packer()
776 		dump_packer_bin(bin, false);  in vdo_dump_packer()